数论——素数筛选法与整数的素因子分解

筛选法   

     求出n以内的素数，最快的应该是筛选法。

 筛选法的思路是：

     要求10000以内的素数，把1-10000都列出来，1不是素数，划掉；2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的所有倍数；直到所有素数找完为止。

     这种做法的空间复杂度是O(n)，时间复杂度O(n/logn)。

const int Max = 1000005;
bool prime[Max]={0};//0表示素数，1为非素数

//筛选n以内的素数
void getPrime(int n)
{
    int i,j;
    int t;
    for(i = 2; i <= n; i++)
    {
        if(!prime[i])
        {
            for(j = 2; (t=j*i) <= n; j++)
                prime[t] = 1;
        }
    }
}

 

 

 

 

分解素因子

     唯一质因子分解定理：任意一个合数a仅能以一种方式，写成如下的乘积形式：

a = p1^e1*p2^e2*...*pr^er

    其中pi为素数，p1<p2<...<pr，且ei为正整数。例如数6000=2^4*3*5^3。

    素因子的分解技巧：首先a的某两个素因子不可能同时大于sqrt(a)，这样，先用筛选法求出sqrt(a)以内的所有素数，然后用a依次去mod这些素数，若能整除，则找到素因子，将素因子去掉，再继续找。最后若a>1，则a也是它的素因子。

 

const int Max = 100005;
int isPrime[Max]={0};
int prime[Max/5],num=0;
int factors[100],s=0;

void getPrime(int n)
{
    int i,j;
    int t;
    for(i = 2; i <= n; i++)
    {
        if(!isPrime[i])
        {
            prime[num++] = i;
            for(j = 2; (t=i*j) <= n; j++)
                isPrime[t] = 1;
        }
    }
}

void decompose(int n, int* factors)
{
    int te = (int)sqrt(n*1.0);
    for(int i = 0; i<num&&prime[i]<=te; i++)
    {
        if(n%prime[i]==0)
        {
            factors[s++] = prime[i];
            while(n%prime[i]==0)
                n = n/prime[i];
        }
    }
    if(n > 1)
        factors[s++] = n;
}

 

 

例

POJ2262

题意：给出任意一个正整数n(n<=10^6)，根据哥德巴赫猜想：任意一个不小于6的整数，都可以表示为两个奇素数之和。问虽任意整数是否满足这个猜想。

解：筛选法将n以内的所有素数都求出来，若a是素数，判断n-a是否为素数，若找到一组不满足，则答案为否定。

 

POJ1142

题意：给一个数n(n<=10^7)，求最小的m>n，使得m的素因子每一位上的数的和 == m的每一位上的数的和。

解：显然这题就是要分解素因子。先求10^4以内的素数，再用素因子分解，然后判断。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int Max = 10005;
bool isPrime[Max]={0};
int prime[Max/4],num=0;

void getPrime(int n)
{
    int t;
    for(int i = 2; i <= n; i++)
    {
        if(isPrime[i]==0)
        {
            prime[num++] = i;
            for(int j = 2; (t=j*i) <= n; j++)
                isPrime[t] = 1;
        }
    }
}

int getSum(int n)
{
    int ret = 0;
    while(n)
    {
        ret += n%10;
        n /= 10;
    }
    return ret;
}

bool isSmith(int n)
{
    int t = (int)sqrt(n*1.0);
    int r1 = getSum(n);
    int r2 = 0;
    int N = n;
    for(int i = 0; i<num&&prime[i]<=t; i++)
    {
        if(n%prime[i]==0)
        {
            int tmpt = getSum(prime[i]);
            while(n%prime[i]==0)
            {
                n = n/prime[i];
                r2 += tmpt;
            }
        }
    }
    if(n > 1)
        r2 += getSum(n);
    if(n==N)
        return false;
    return r1==r2;
}

int main()
{
    int i;
    int n;
    getPrime(Max-1);
    while(true)
    {
        scanf("%d",&n);
        if(!n)
            break;
        for(i = n+1; ;i++)
        {
            if(isSmith(i))
                break;
        }
        printf("%d\n",i);
    }
    return 0;
}