さいしょうしつりょういんし

さいしょうしつりょういんし
オーラリニアスクリーン実装
原理:オーラ線形ふるい素数法で、各数はその最小素因数ふるいを使用するだけである.

#include 
 
using namespace std;
 
inline int mini(int a, int b) {return a < b ? a : b;}
 
//               
const int LIM = 1e6 + 10;       /* The limit of number to be test */
int prime[LIM / 3];
int miniFactor[LIM];
int primepos;
void euler() {
    int tmp;
    for (int i = 2; i < LIM; i++) {
        if (!miniFactor[i]) prime[primepos++] = i, miniFactor[i] = i;
        for (int j = 0; (tmp = i * prime[j]) < LIM; j++) {
            miniFactor[tmp] = prime[j];
            if (!(i % prime[j])) break;
        }
    }
}
 
// test program
int main(void) {
    euler();
    for (int i = 1; i <= 10; i++) {
        printf("the mini factor of %d is %d
", i, miniFactor[i]);
    }
    printf("the mini factor of 47 is %d
", miniFactor[47]);
    printf("the mini factor of 61 is %d
", miniFactor[61]);
    printf("the mini factor of 561 is %d
", miniFactor[561]);
 
    return 0;
}