算法-极品素数 --参与有奖

冬冬

极品素数：如果一组素数从1开始编号，如果他的序号也是素数，那么这个素数就称极品素数。
例：
2、3、5、7、11、13、17、19......
1、2、3、4、 5、  6、 7、  8、  9......
那么3、5、11、17就为极品素数。。。
统计N以内的所有极品素数个数
2<=N<=100000
测试时间为2秒

输入输出实例：
输入：20
输出：4



参与回帖的代码，活动结束后公开

仰望天上的光

1.LZ题目出错了，9=3*3,所以9不是素数，所以9不是极品素数
2.贴我的代码

1. #include<stdio.h>
   
2. #define NUMS 100000
   
3. #define SQRT_NUMS 316
   
4. 
   
5. static int vec[NUMS+1];
   
6. 
   
7. /*
   
8. 筛法求素数
   
9. (1)vec[i]==0则i为素数
   
10. (1)vec中下标为偶数的肯定不是素数
    
11. */
    
12. void initTable();
    
13. //计算极品素数的个数
    
14. int count(int n);
    
15. 
    
16. int main(){
    
17.         int number;
    
18.         initTable();
    
19.         while(scanf("%d",&number)!=EOF){
    
20.                 printf("%d\n",count(number));
    
21.         }
    
22. }
    
23. 
    
24. void initTable(){
    
25.         int i,j;
    
26.         for(i=3;i<=SQRT_NUMS;++i){
    
27.                 if(vec[i]==0){
    
28.                         for(j=i*i;j<=NUMS;j+=2*i)
    
29.                                 vec[j]=1;
    
30.                 }
    
31.         }
    
32. }
    
33. 
    
34. int count(int n){
    
35.         //2是极品素数
    
36.         int result = 1;
    
37.         //第几个素数
    
38.         int priNumber = 1;
    
39.         int i;
    
40.         if(n<2) return 0;
    
41.         for(i=5;i<=n;i+=2){
    
42.                 if(vec[i]==0) {
    
43.                         ++priNumber;
    
44.                         if( priNumber%2 && vec[priNumber] == 0 ){
    
45.                                 result++;
    
46.                         }
    
47.                 }
    
48.         }
    
49.         return result;
    
50. }
    

复制代码

冬冬

仰望天上的光 发表于 2011-7-23 13:13

                               
登录/注册后可看大图

1.LZ题目出错了，9=3*3,所以9不是素数，所以9不是极品素数
2.贴我的代码

你的initTable函数做法让我郁闷，这样筛选的素数表能解释一下吗？ 用来统计极品素数结果是大部分正确的，刚才又看了看，结果出现了一点异常。当我输入1万时，结果与我的相差1。
这是我的代码，嘿嘿用的是迭代法。:lol

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. bool super(int x);
   
5. int count(int n);
   
6. void print(int n);
   
7. int main()
   
8. {
   
9.     int number;
   
10.     cin>>number;
    
11.     //print(number);
    
12.     cout<<count(number)<<endl;
    
13.     system("pause");
    
14.     return 0;
    
15. }bool super(int x)
    
16. {
    
17.      bool flag=true;
    
18.      if(x<2)
    
19.      {
    
20.             return false;
    
21.      }
    
22.      if(x==2)
    
23.              return true;
    
24.      else
    
25.      {
    
26.          for(int i=2;i<=sqrt(x);i++)
    
27.          {
    
28.                  if(x%i==0)
    
29.                  {
    
30.                            flag=false;
    
31.                            break;
    
32.                  }
    
33.          }
    
34.      }
    
35.      return flag;
    
36. }
    
37. int count(int n)
    
38. {
    
39.      int c=0;
    
40.      int item=0;
    
41.      int i;
    
42.      for(i=2;i<=n;i++)
    
43.      {
    
44.         if(super(i))
    
45.                     item++;
    
46.             if( super(i) && super(item))
    
47.             {
    
48.                 c++;
    
49.                // cout<<i<<endl;
    
50.             }
    
51.      }
    
52.      return c;
    
53. }void print(int n)
    
54. {
    
55.      for(int i=2;i<=n;i++)
    
56.      {
    
57.              if(super(i))
    
58.                          cout<<i<<"\t";
    
59.      }
    
60.      cout<<endl;
    
61. }
    
62. 
    

复制代码

冬冬

elyric 发表于 2011-7-23 17:41

                               
登录/注册后可看大图

结果错误

仰望天上的光

我的程序有问题，改2个地方：
（1）38行改为int priNumber = 2;因为我从5开始检测，5之前已经有2个素数2和3了。（这个影响了程序的正确性，改后结果和LZ的一样）
（2）26行改为 for(i=3;i<=SQRT_NUMS;i+=2)，这样运行效率更高些。
筛法的说明，我从百度百科copy过来给大家看看
筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛法（sieve of Eratosthenes）。
具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛法”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

      在这个基本的筛法基础上，我作了一些改进。以求10000内的素数为例，只要先求出100内的所有素数，然后，以100内的这些素数为筛子，可以把10000内所有的非素数筛掉。
      证明：假设某个大于100小于10000的合数没被筛掉，把它分解质因数，这些质因数里最小的，一定大于100（否则该数就会被100内的素数筛掉），但大于100的两个质因数的乘积一定大于10000.与假设矛盾，证毕。
      根据这个推论，要把100000的合数筛掉，就要求出1~100000平方根（316.XX）的素数。这就是initTable中for(i=3;i<=SQRT_NUMS;++i)循环的含义。此外当你得到一个素数，即if(vec[i]==0)的时候，说明1~i*i的合数都已经被筛掉了（见前面的证明）。所以从i*i往后筛就可以了。
      还有一个因素可以帮助提高程序效率，就是所有的偶数位置肯定不是素数（2我作了特殊处理），所以筛的时候，步长可以选2*i(选i为步长的话每2步肯定出现一个偶数，偶数就不会是素数)。同理外层for循环步长也可以为2.
最终修正好的程序如下：（原来出错的地方都被我注释掉了）

1. #include<stdio.h>
   
2. #define NUMS 100000
   
3. #define SQRT_NUMS 316
   
4. 
   
5. static int vec[NUMS+1];
   
6. 
   
7. /*
   
8. 筛法求素数
   
9. (1)vec[i]==0则i为素数
   
10. (1)vec中下标为偶数的肯定不是素数
    
11. */
    
12. void initTable();
    
13. //计算极品素数的个数
    
14. int count(int n);
    
15. 
    
16. int main(){
    
17.         int number;
    
18.         initTable();
    
19.         while(scanf("%d",&number)!=EOF){
    
20.                 printf("%d\n",count(number));
    
21.         }
    
22. }
    
23. 
    
24. void initTable(){
    
25.         int i,j;
    
26.         //for(i=3;i<=SQRT_NUMS;++i){
    
27.                 for(i=3;i<=SQRT_NUMS;i+=2){
    
28.                 if(vec[i]==0){
    
29.                         for(j=i*i;j<=NUMS;j+=2*i)
    
30.                                 vec[j]=1;
    
31.                 }
    
32.         }
    
33. }
    
34. 
    
35. int count(int n){
    
36.         //2是极品素数
    
37.         int result = 1;
    
38.         //第几个素数
    
39.         //int priNumber = 1;
    
40.                 int priNumber = 2;
    
41.         int i;
    
42.         if(n<2) return 0;
    
43.         for(i=5;i<=n;i+=2){
    
44.                 if(vec[i]==0) {
    
45.                         ++priNumber;
    
46.                         if( priNumber%2 && vec[priNumber] == 0 ){
    
47.                             result++;
    
48.                         }
    
49.                 }
    
50.         }
    
51.         return result;
    
52. }

复制代码

冬冬

仰望天上的光 发表于 2011-7-23 22:25

                               
登录/注册后可看大图

我的程序有问题，改2个地方：
（1）38行改为int priNumber = 2;因为我从5开始检测，5之前已经有2个素数2和 ...

我一直纳闷的是，我给你的代码添加了一个PrintTable函数，打印了2 - 100之间的素数，如下图。但是这个表用来统计极品素数，结果确实对的

1. #include<stdio.h>
   
2. 
   
3. #define NUMS 100000
   
4. 
   
5. #define SQRT_NUMS 316
   
6. static int vec[NUMS+1];
   
7. /*
   
8. 
   
9. 筛法求素数
   
10. 
    
11. (1)vec[i]==0则i为素数
    
12. 
    
13. (1)vec中下标为偶数的肯定不是素数
    
14. 
    
15. */
    
16. 
    
17. void initTable();
    
18. 
    
19. //计算极品素数的个数
    
20. 
    
21. int count(int n);
    
22. 
    
23. void PrintTable()
    
24. {
    
25.      for(int i=2;i<=100;i++)
    
26.      {
    
27.              if(vec[i]==0)  
    
28.                             printf("%d\t",i);
    
29.      }
    
30.      printf("\n");
    
31. }
    
32. int main(){
    
33. 
    
34.         int number;
    
35. 
    
36.         initTable();
    
37.         PrintTable();
    
38. 
    
39.         while(scanf("%d",&number)!=EOF){
    
40. 
    
41.                 printf("%d\n",count(number));
    
42. 
    
43.         }
    
44. 
    
45. }
    
46. void initTable(){
    
47. 
    
48.         int i,j;
    
49. 
    
50.         //for(i=3;i<=SQRT_NUMS;++i){
    
51. 
    
52.                 for(i=3;i<=SQRT_NUMS;i+=2){
    
53. 
    
54.                 if(vec[i]==0){
    
55. 
    
56.                         for(j=i*i;j<=NUMS;j+=2*i)
    
57. 
    
58.                                 vec[j]=1;
    
59. 
    
60.                 }
    
61. 
    
62.         }
    
63. 
    
64. }
    
65. int count(int n){
    
66. 
    
67.         //2是极品素数
    
68. 
    
69.         int result = 1;
    
70. 
    
71.         //第几个素数
    
72. 
    
73.         //int priNumber = 1;
    
74. 
    
75.                 int priNumber = 2;
    
76. 
    
77.         int i;
    
78. 
    
79.         if(n<2) return 0;
    
80. 
    
81.         for(i=5;i<=n;i+=2){
    
82. 
    
83.                 if(vec[i]==0) {
    
84. 
    
85.                         ++priNumber;
    
86. 
    
87.                         if( priNumber%2 && vec[priNumber] == 0 ){
    
88. 
    
89.                             result++;
    
90. 
    
91.                         }
    
92. 
    
93.                 }
    
94. 
    
95.         }
    
96. 
    
97.         return result;
    
98. 
    
99. }
    
100. 
     

复制代码

仰望天上的光

原版initTable中的问题只影响效率，不影响结果。（即素数表的结果是正确的）
主要是count函数中的修改影响正确性。你并没有测试count函数

紫色枫叶

仰望天上的光 发表于 2011-7-23 22:25

                               
登录/注册后可看大图

我的程序有问题，改2个地方：
（1）38行改为int priNumber = 2;因为我从5开始检测，5之前已经有2个素数2和 ...

的确很厉害.不过我想问一下,是否可以再作如此修整

1. void initTable()
   
2. {
   
3.         int i,j;
   
4.         //for(i=3;i<=SQRT_NUMS;++i){
   
5.         for(i=3;i<=SQRT_NUMS;i+=2)
   
6.         {
   
7.                 //vec[i - 1] = 1;
   
8.                 vec[i + 1] = 1;
   
9.                 if(vec[i]==0)
   
10.                 {
    
11.                         for(j=i*i;j<=NUMS;j+=2*i)
    
12.                                 vec[j]=1;
    
13.                 }
    
14.         }
    
15. }
    
16. 我还是多此一举了。会错意了。
    

复制代码

紫色枫叶

冬冬 发表于 2011-7-23 22:44

                               
登录/注册后可看大图

我一直纳闷的是，我给你的代码添加了一个PrintTable函数，打印了2 - 100之间的素数，如下图。但是这个 ...

我在你修改仰望天上的光的基础,又进行了一点调整,可以统计极品素数的个数并输出预期的极品素数。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define NUMS 100000
   
5. #define SQRT_NUMS 318
   
6. 
   
7. static int vec[NUMS+1];
   
8. 
   
9. /*
   
10. 筛法求素数
    
11. (1)vec[i]==0则i为素数
    
12. (1)vec中下标为偶数的肯定不是素数
    
13. */
    
14. void initTable();
    
15. //计算极品素数的个数
    
16. int count(int n);
    
17. void PrintAndCount(int n)
    
18. {
    
19.     /* for(int i = 2;i <= n; i++)
    
20.      {
    
21.                 if(vec[i] == 0)  
    
22.                         printf("%d\t",i);
    
23.      }
    
24.      printf("\n");*/
    
25.         int result = 0;
    
26.         int priNumber = 2;
    
27.         for(int i = 3; i <= n; i++)
    
28.         {
    
29.                 if(vec[i] == 0)
    
30.                 {
    
31.                         if(i % 2 && vec[priNumber] == 0)
    
32.                         {
    
33.                                 printf("%d\t", i);
    
34.                                 result++;
    
35.                         }
    
36.                         priNumber++;
    
37.                 }
    
38.         }
    
39.         printf("\n共有%d个极品素数\n", result);
    
40. }
    
41. int main(int argc, char **argv)
    
42. {
    
43.         int number;
    
44.         initTable();
    
45.     while(scanf("%d", &number) != EOF)
    
46.         {
    
47.                 if(number == -1)
    
48.                         break;
    
49.                 PrintAndCount(number);
    
50.         }
    
51.         system("pause");
    
52.         return 0;
    
53. }
    
54. 
    
55. void initTable()
    
56. {
    
57.         int i ,j, k;
    
58.                 for(k = 4; k <= NUMS; k += 2)
    
59.                 {
    
60.                         vec[k] = 1;
    
61.                 }
    
62.         for(i = 3; i <= SQRT_NUMS; i += 2)
    
63.                 {
    
64.                         if(vec[i] == 0)
    
65.                         {        
    
66.                                 for(j = i * i; j <= NUMS; j += 2 * i)
    
67.                                         vec[j] = 1;
    
68.             }
    
69.         }
    
70. }

复制代码

冬冬

紫色枫叶 发表于 2011-7-24 16:36

                               
登录/注册后可看大图

我在你修改仰望天上的光的基础,又进行了一点调整,可以统计极品素数的个数并输出预期的极品素数。

他的筛法，是转为此题而设计的。

断点

楼主，，，  那个2好像也是极品素数吧

冬冬

断点 发表于 2011-7-24 19:21

                               
登录/注册后可看大图

楼主，，，  那个2好像也是极品素数吧

我们的题目，第一个素数是2，不是从1开始的。虽然有些书上说1也是素数

Be_envious

素数 只能被1和他本身整除的数

tcwz

可惜我连素数是什么都不知道

redguy

后悔当年没有好好学数据结构O(∩_∩)O~

785131460

#include<stdio.h>
#include<math.h>
int f(int n)
{
        int i,j,count=1;
        for(i=3;i<=n;i++){
                for(j=2;j<=sqrt(n);j++)
                        if(i%j==0) break;
                        if(j>=sqrt(n)) count++;
        }
        return count;
}
int main()
{
        int N,M;
        scanf("%d",&N);
        M=f(N);
        printf("%d\n",f(M));
        return 0;
}
       

丿夏夜灬彬刂

见识咯 都是大神啊 高手 继续努力

梦幻羽羽

呵呵。。。  极品素数？  头一次听说  顶一个0.0