素數專題

[cpp]
#include <iostream> 
#include <cmath> 
 
using namespace std; 
const int nMax = 10000000; 
int isPrime[nMax]; 
int prime[nMax]; 
int factor[nMax]; 
int len; 
 
 
void f1()//樸素篩選 
{ 
    int n;//求[1, n]之間的素數 
    scanf("%d", &n); 
    len = 0; 
    memset(isPrime, 0, sizeof(isPrime)); 
    isPrime[0] = isPrime[1] = 1; 
    int i; 
    for(i = 2; i <= n; ++ i) 
    { 
        if(!isPrime[i]) 
        { 
            prime[len ++] = i; 
            isPrime[i] = 1; 
            __int64 j; 
            for(j = (__int64)i * i; j <= n; j += i)//這裡i * i會越界 
                isPrime[j] = 1; 
        } 
    } 
} 
 
void f2()//線性篩選。在f1上進行改裝，每次查找合數時，使用該合數的最小質因子尋找。速度可提高2倍，但是我感覺不太出來 
{ 
    int n;//求[1, n]之間的素數 
    scanf("%d", &n); 
    len = 0; 
    memset(isPrime, 0, sizeof(isPrime)); 
    isPrime[0] = isPrime[1] = 1; 
    int i; 
    for(i = 2; i <= n; ++ i) 
    { 
        if(!isPrime[i]) 
            prime[len ++] = i; 
        int j; 
        for(j = 0; j < len && i * prime[j] <= n; ++ j) 
            //每次更新一個i，則對所有素數遍歷一次。如果發現i是其中素數的倍數，則跳出循環，這樣避免重復運算 
        { 
            isPrime[i * prime[j]] = 1; 
            if(i % prime[j] == 0) 
                break; 
        } 
    } 
} 
 
int max(int a, int b) 
{ 
    return a > b ? a : b; 
} 
 
void f3()//區間內求素數，兩點，第一：兩數相乘篩選出所有的合數。第二：使用移動數組做標記 
{ 
    int a, b;//求區間[a,b]之間的所有素數 
    scanf("%d%d", &a, &b); 
    if(a == 1) a ++;//1的時候需要特殊判斷，因為永遠標記不到 
    int m = sqrt(b + 0.5); 
    int i; 
    for(i = 2; i <= m; ++ i) 
    { 
        int j; 
        for(j = max(i, a / i); j <= b / i; ++ j) 
            if(i * j - a >= 0) 
                isPrime[i * j - a] = 1; 
    } 
    len = 0; 
    for(i = a; i <= b; ++ i) 
        if(!isPrime[i - a]) 
            prime[len ++] = i; 
 
} 
 
void f4()//最小質因數，函數與f2()很相似 
{ 
    int n;//求[1,n]所有數的質因數 
    scanf("%d", &n); 
    memset(isPrime, 0, sizeof(isPrime)); 
    len = 0; 
    int i; 
    factor[1] = 1; 
    for(i = 2; i <= n; ++ i) 
    { 
        if(!isPrime[i]) 
        { 
            prime[len ++] = i; 
            factor[i] = i; 
        } 
        int j; 
        for(j = 0; j < len && i * prime[j] <= n; ++ j) 
        { 
            isPrime[i * prime[j]] = 1; 
            factor[i * prime[j]] = prime[j]; 
            if(i % prime[j] == 0) 
                break; 
        } 
    } 
    for(i = 1; i <= n; ++ i) 
    { 
        printf("i = %d, factor = %d\n", i, factor[i]); 
    } 
} 
 
void print() 
{ 
    int i; 
    for(i = 0; i < len; ++ i) 
    { 
        printf("%d\t", prime[i]); 
        if((i + 1) % 5 == 0) 
            printf("\n"); 
    } 
    printf("\n"); 
} 
 
int main() 
{ 
    /*
    f1();
    print();
    f2();
    print();
    f3();
    print();*/ 
    f4(); 
    return 0; 
} 
作者：lhshaoren