基于題目的--素數篩法

資料來源：

1，https://blog.csdn.net/tomorrowtodie/article/details/51865496

2，https://blog.csdn.net/Danliwoo/article/details/48827813#fn:meison

3，https://blog.csdn.net/u012717411/article/details/43412043

4，https://blog.csdn.net/z690933166/article/category/1349672/3

5，https://blog.csdn.net/lianai911/article/category/2562225/4

6，https://blog.csdn.net/bigbigship/article/category/1931643/6

7，http://www.cnblogs.com/tom987690183/p/3260724.html

素數篩法

很多數學題裡面都有用到，主要就是卡逾時的問題。

不多說，直接上三種模闆：

素數篩法一：（最簡單的）

#include<iostream>
#include<cstring>
#include<cstdio>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf (1<<29)
using namespace std;
typedef long long ll;
const int N = 100;
bool p[N+5];
void init()
{
    mem(p,1);
    for (int i = 2;i*i <= N;++i)
    {
        if (p[i])
        {
            for (int j = i*i;j <= N;j+=i)
            {
                p[j] = 0;
            }
        }
    }
}
int main()
{
    init();
    for (int i = 2;i <= N;++i)
    {
        if (p[i]) cout<<i<<endl;
    }
    return 0;
}
           

素數篩法二：

#include<iostream>
#include<cmath>
#include<cstdio>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf (1<<29)
using namespace std;
typedef long long ll;
const int N = 100;
int p[N+5];
void init()
{
    int sq = (int)sqrt(N*2+1);
    for (int i = 3;i <= sq;i+=2)
    {
        if (p[i>>1]) continue;
        for (int j = i*i;j <= N<<1;j+=i<<1)
        {
            p[j>>1] = 1;
        }
    }
}
int main()
{
    init();
    puts("2");
    for (int i = 1;i < N;++i)
    {
        if (p[i]) continue;
        printf("%d\n",(i<<1)+1);
    }
    return 0;
}
           

素數篩法三：

#include<iostream>
#include<cstring>
#include<cstdio>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf (1<<29)
using namespace std;
typedef long long ll;
const int N = 100000;
int a[N+5];
int p[N+5];
void init()
{
    int t = 0;
    for (int i = 2;i <= N;++i)
    {
        if (a[i] == 0)
        {
            p[++t] = i;
        }
        for (int j = 1,k;(j<=t)&&(k=i*p[j])<=N;++j)
        {
            a[k] = 1;
            if (i%p[j]==0) break;
        }
    }
}
int main()
{
    init();
    for (int i = 1;p[i]>1;++i)
    {
        printf("%d\n",p[i]);
    }
    return 0;
}
           

素數篩法

• 埃拉托斯尼斯篩法 

  先将2~N内所有的數标記為素數，從最小的素數開始篩去其倍數，再找到下一個素數，依次篩去非素數的數，剩餘的即為素數。 

  需要篩的素數範圍隻需在2~N−−√N.

在POJ 2689，可以節省空間大小。

• 6N±±1篩法 

  由于6N，6N+2，6N+3，6N+4（N>0）均不是素數，故在篩素數時可以直接從6N±±1中判斷和篩選素數。

素數（質數）指的是指大于一的自然數 的因子隻有它本身和1的數，1,0不是素數也不是合數。

方法一：一個數 n如果是合數，那麼它的所有的因子不超過sqrt(n)--n的開方,是以，判定單個數是否是素數通常是通過這個原理,求a是否為素數，做一個小于等于sqrt(a)的循環即可判定。複雜度是o(n*sqrt(n))

int num=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
                break;
            if(j*j>i)
            {
                prime[num++]=i;
            }
        }
    }
           

方法二：埃拉托色尼(Eratosthenes)篩法

這種篩法在N為10^6甚至更大時可以很快速的求出1到N之間的所有素數，把之前找到的素數的倍數标記為合數，沒被标記的自然為素數，時間複雜度o(nloglog(n)),這種方法在解決一般的素數問題中足矣。

bool prime[N];
int p[N];
int k=0;
void isprime(int n)
{
    long long i,j;
    memset(prime,true,sizeof(prime));
    for(int i=2;i<=n;i++)
    {
        if(prime[i])
        {
            p[k++]=i;
            {
                for(int j=i*i;j<n;j+=i)
                {
                    prime[j]=false;
                }
            }
        }
    }
} 
           

方法三：線性篩法   它與埃拉托色尼篩法類似，但它保證使得任何一個合數，隻被它最小的質因數标記過一次。是以整個算法是線性的。 時間複雜度為o(n),但就實際問題而言，埃拉托色尼篩法和線性篩法在運算速度上并沒有太大的差別

bool prime[N];
int p[N];
void Init()
{
     int cnt = 0;
     memset(prime,true,sizeof(prime));
      for (int i = 2; i < N; i++)
      {
          if (prime[i])
                p[cnt++] = i;
          for (int j = 0; j < cnt && p[j] * i < N; j++)
          {
              prime[i*p[j]] = false;
             if (i % p[j] == 0)
                 break;
         }
     }
 }
           

POJ2739_Sum of Consecutive Prime Numbers【篩法求素數】【枚舉】

Sum of Consecutive Prime Numbers

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 19350 Accepted: 10619

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime 

numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. 

Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

2

3

17

41

20

666

12

53

Sample Output

1

1

2

3

1

2

Source

Japan 2005

題目大意：

一個數可以由若幹種連續的素數序列求和得到，比如說41 = 2+3+5+7+11+13 = 11+13+17 = 41

共有三種不同的素數序列求和得到。給你一個數N，求滿足N = 連續的素數序列和的方案數

思路：

很簡單的題目，但是用普通方法判斷素數可能會逾時，這裡用了篩法求素數的方法直接用數組Prime

判斷是否為素數，另開一個數組PrimeNum用來存所有的素數。

最後就是枚舉，求得滿足的方案數

#include<stdio.h>
#include<string.h>
 
int Prime[10010],PrimeNum[10010];
 
int IsPrime()//篩法求素數
{
    Prime[0] = Prime[1] = 0;
 
    for(int i = 2; i <= 10000; i++)
        Prime[i] = 1;
    for(int i = 2; i <= 10000; i++)
    {
        for(int j = i+i; j <= 10000; j+=i)
            Prime[j] = 0;
    }
    int num = 0;
    for(int i = 0; i <= 10000; i++)
        if(Prime[i])
            PrimeNum[num++] = i;
 
    return num;
}
int main()
{
    int num = IsPrime();
    int N;
    while(~scanf("%d",&N) && N!=0)
    {
        int count = 0;
        for(int i = 0; PrimeNum[i]<=N && i < num; i++)//枚舉
        {
            int sum = 0;
            for(int j = i; PrimeNum[j]<=N && j < num; j++)
            {
                sum += PrimeNum[j];
                if(sum == N)
                {
                    count++;
                    break;
                }
                if(sum > N)
                    break;
            }
        }
 
        printf("%d\n",count);
    }
 
    return 0;
}