配列 a に n 個の整数が格納されています。たとえば、a[0]、a[1]、.....、a[n-1] で、それぞれa[i] <= 10^12とn <100. ここで、これらの n 個の整数の最小公倍数 ({a[0],a[1],.....,a[n-1]} の最小公倍数) のすべての素因数を見つける必要があります。
方法はありますが、より効率的な方法が必要です。
私の方法：
First calculate all the prime numbers up to 10^6 using sieve of Eratosthenes.
For each a[i]
bool check_if_prime=1;
For all prime <= sqrt(a[i])
if a[i] % prime[i] == 0 {
store prime[i]
check_if_prime=0
}
if check_if_prime
store a[i] // a[i] is prime since it has no prime factor <= sqrt(n)
Print all the stored prime[i]'s
この問題に対するより良いアプローチはありますか?
問題へのリンクを投稿しています：
http://www.spoj.pl/problems/MAIN12B/
私のコードへのリンク: http://pastebin.com/R8TMYxNz
解決：
Daniel Fischer が提案したように、私のコードには、ふるいの高速化やマイナーな変更などの最適化が必要でした。これらすべての変更を行った後、問題を解決できました。これは、1.05 秒かかった SPOJ で受け入れられたコードです。
#include<iostream>
#include<cstdio>
#include<map>
#include<bitset>
using namespace std;
#define max 1000000
bitset <max+1> p;
int size;
int prime[79000];
void sieve(){
size=0;
long long i,j;
p.set(0,1);
p.set(1,1);
prime[size++]=2;
for(i=3;i<max+1;i=i+2){
if(!p.test(i)){
prime[size++]=i;
for(j=i;j*i<max+1;j++){
p.set(j*i,1);
}
}
}
}
int main()
{
sieve();
int t;
scanf("%d", &t);
for (int w = 0; w < t; w++){
int n;
scanf("%d", &n);
long long a[n];
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
map < long long, int > m;
map < long long, int > ::iterator it;
for (int i = 0; i < n; i++){
long long num = a[i];
long long pp;
for (int j = 0; (j < size) && ((pp = prime[j]) * pp <= num); j++){
int c = 0;
for ( ; !(num % pp); num /= pp)
c = 1;
if (c)
m[pp] = 1;
}
if ((num > 0) && (num != 1)){
m[num] = 1;
}
}
printf("Case #%d: %d\n", w + 1, m.size());
for (it = m.begin(); it != m.end(); it++){
printf("%lld\n", (*it).first);
}
}
return 0;
}
場合によっては、誰かがより良い方法またはより速い方法でそれを行うことができる場合は、私に知らせてください.