基于题目的--素数筛法

资料来源：

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
0
Sample Output


1
1
2
3
0
0
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;
}