素数专题

[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