حل سوال 347 ProjectEuler

#include <iostream>
#include <set>
#include <map>
#include <cstdio>
#include <numeric>
#include <cstring>

using namespace std;

const int oo = 10000000;
const int maxn = 5000001;
int num,prime[1000000];
bool isNotPrime[maxn + 5];
int Eratosthenes(int n){
	int num = 0;
	isNotPrime[0] = isNotPrime[1] = true;
	for(int i = 2;i <= n; ++i){
		if(!isNotPrime[i]) prime[num++] = i;
		for(int j = 0;j < num && i * prime[j] <= n; ++j){
			isNotPrime[i * prime[j]] = true;
			if(i % prime[j] == 0) break;
		}
	}
	return num;
}
int main() {
	num = Eratosthenes(maxn);
//	printf("%d\n",num);
	int r = num - 1;
	printf("%d\n",prime[0]);
	long long ans = 0;
	while(r > 0){
		int l = 0;
		while(l < r && prime[l] * prime[r] <= oo){
			long long adder = 1;
			long long tl = prime[l];
			for(int i = 0;tl <= oo;){
				long long tr = prime[r];
				for(int j = 0;tr <= oo;){
					long long now = tr * tl;
					if(now <= oo) adder = max(adder,now);
					tr *= prime[r];
				}
				tl *= prime[l];
			}
			ans += adder;
			l++;
		}
		r--;
	}
	printf("%lld\n",ans);
}

   لینک سوال در ProjectEuler