# Why is my solution timing out? (USACO 2020 Gold Open P3 Exercise)

I checked my code and it should have the exact same run time as the official solution: my code iterates i through [0, q=primes.size()], x through [0, N], and j through [1, log(x)]. The official code iterates i through [0, primes.size()], j through [0, N], and pp through log(j) iterations.

This means the two programs should have the exact same runtime, but mine is timing out for some reason.

My code:

``````#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <numeric>
using namespace std;
using ll=long long;

int N, q=0, sieve;
ll M, f;
vector<int> p={0};

void sieveMethod(){
for (int i=2; i<=N; i++) sieve[i]=0;
for (int x=2; x<=N; x++){
if (sieve[x]==0){
for (int j=2*x; j<=N; j+=x) sieve[j]=x;
q++;
}
}
for (int i=2; i<=N; i++){
if (sieve[i]==0) p.push_back(i);
}
}

int main() {
ifstream cin("exercise.in");
cin>>N>>M;
sieveMethod();
for (int i=0; i<=q; i++) f[i]=1;
for (int i=0; i<=N; i++) f[i]=1;
for (int i=1; i<=q; i++){
for (int x=1; x<=N; x++){
f[x][i]=f[x][i-1];
int m=(int)(log(x)/log(p[i]));
for (int j=1; j<=m; j++){
int pj=(int)(pow(p[i], j));
}
}
}
ofstream fout("exercise.out");
fout<<f[N][q];
}
``````

It’s probably something related to `m`. When I replaced your third for loop with a while loop like this:

``````#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <vector>
using namespace std;
using ll=long long;

int N, q=0, sieve;
ll M, f;
vector<int> p={0};

void sieveMethod(){
for (int i=2; i<=N; i++) sieve[i]=0;
for (int x=2; x<=N; x++){
if (sieve[x]==0){
for (int j=2*x; j<=N; j+=x) sieve[j]=x;
q++;
}
}
for (int i=2; i<=N; i++){
if (sieve[i]==0) p.push_back(i);
}
}

int main() {
ifstream cin("exercise.in");
cin>>N>>M;
sieveMethod();
for (int i=0; i<=q; i++) f[i]=1;
for (int i=0; i<=N; i++) f[i]=1;
for (int i=1; i<=q; i++){
for (int x=1; x<=N; x++){
f[x][i]=f[x][i-1];
int m=(int)(log(x)/log(p[i]));
int pj = p[i];
while(pj <= x){
pj *= p[i];
}
}
}
ofstream fout("exercise.out");
fout<<f[N][q];
}
``````

Probably `log` is just slow?