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

冬冬

极品素数：如果一组素数从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.贴我的代码

#include<stdio.h>
#define NUMS 100000
#define SQRT_NUMS 316

static int vec[NUMS+1];

/*
筛法求素数
(1)vec[i]==0则i为素数
(1)vec中下标为偶数的肯定不是素数
*/
void initTable();
//计算极品素数的个数
int count(int n);

int main(){
        int number;
        initTable();
        while(scanf("%d",&number)!=EOF){
                printf("%d\n",count(number));
        }
}

void initTable(){
        int i,j;
        for(i=3;i<=SQRT_NUMS;++i){
                if(vec[i]==0){
                        for(j=i*i;j<=NUMS;j+=2*i)
                                vec[j]=1;
                }
        }
}

int count(int n){
        //2是极品素数
        int result = 1;
        //第几个素数
        int priNumber = 1;
        int i;
        if(n<2) return 0;
        for(i=5;i<=n;i+=2){
                if(vec[i]==0) {
                        ++priNumber;
                        if( priNumber%2 && vec[priNumber] == 0 ){
                                result++;
                        }
                }
        }
        return result;
}

冬冬

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

                               
登录/注册后可看大图

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

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

#include <iostream>
#include <cmath>
using namespace std;
bool super(int x);
int count(int n);
void print(int n);
int main()
{
    int number;
    cin>>number;
    //print(number);
    cout<<count(number)<<endl;
    system("pause");
    return 0;
}bool super(int x)
{
     bool flag=true;
     if(x<2)
     {
            return false;
     }
     if(x==2)
             return true;
     else
     {
         for(int i=2;i<=sqrt(x);i++)
         {
                 if(x%i==0)
                 {
                           flag=false;
                           break;
                 }
         }
     }
     return flag;
 }
 int count(int n)
{
     int c=0;
     int item=0;
     int i;
     for(i=2;i<=n;i++)
     {
        if(super(i))
                    item++;
            if( super(i) && super(item))
            {
                c++;
               // cout<<i<<endl;
            }
     }
     return c;
 }void print(int n)
{
     for(int i=2;i<=n;i++)
     {
             if(super(i))
                         cout<<i<<"\t";
     }
     cout<<endl;
 }

 

冬冬

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.
最终修正好的程序如下：（原来出错的地方都被我注释掉了）

#include<stdio.h>
#define NUMS 100000
#define SQRT_NUMS 316

static int vec[NUMS+1];

/*
筛法求素数
(1)vec[i]==0则i为素数
(1)vec中下标为偶数的肯定不是素数
*/
void initTable();
//计算极品素数的个数
int count(int n);

int main(){
        int number;
        initTable();
        while(scanf("%d",&number)!=EOF){
                printf("%d\n",count(number));
        }
}

void initTable(){
        int i,j;
        //for(i=3;i<=SQRT_NUMS;++i){
                for(i=3;i<=SQRT_NUMS;i+=2){
                if(vec[i]==0){
                        for(j=i*i;j<=NUMS;j+=2*i)
                                vec[j]=1;
                }
        }
}

int count(int n){
        //2是极品素数
        int result = 1;
        //第几个素数
        //int priNumber = 1;
                int priNumber = 2;
        int i;
        if(n<2) return 0;
        for(i=5;i<=n;i+=2){
                if(vec[i]==0) {
                        ++priNumber;
                        if( priNumber%2 && vec[priNumber] == 0 ){
                            result++;
                        }
                }
        }
        return result;
}

冬冬

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

                               
登录/注册后可看大图

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

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

#include<stdio.h>
 
#define NUMS 100000
 
#define SQRT_NUMS 316
 static int vec[NUMS+1];
 /*
 
筛法求素数
 
(1)vec[i]==0则i为素数
 
(1)vec中下标为偶数的肯定不是素数
 
*/
 
void initTable();
 
//计算极品素数的个数
 
int count(int n);
 
void PrintTable()
{
     for(int i=2;i<=100;i++)
     {
             if(vec[i]==0)  
                            printf("%d\t",i);
     }
     printf("\n");
 }
int main(){
 
        int number;
 
        initTable();
        PrintTable();
 
        while(scanf("%d",&number)!=EOF){
 
                printf("%d\n",count(number));
 
        }
 
}
 void initTable(){
 
        int i,j;
 
        //for(i=3;i<=SQRT_NUMS;++i){
 
                for(i=3;i<=SQRT_NUMS;i+=2){
 
                if(vec[i]==0){
 
                        for(j=i*i;j<=NUMS;j+=2*i)
 
                                vec[j]=1;
 
                }
 
        }
 
}
 int count(int n){
 
        //2是极品素数
 
        int result = 1;
 
        //第几个素数
 
        //int priNumber = 1;
 
                int priNumber = 2;
 
        int i;
 
        if(n<2) return 0;
 
        for(i=5;i<=n;i+=2){
 
                if(vec[i]==0) {
 
                        ++priNumber;
 
                        if( priNumber%2 && vec[priNumber] == 0 ){
 
                            result++;
 
                        }
 
                }
 
        }
 
        return result;
 
}

 

仰望天上的光

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

紫色枫叶

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

                               
登录/注册后可看大图

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

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

void initTable()
{
        int i,j;
        //for(i=3;i<=SQRT_NUMS;++i){
        for(i=3;i<=SQRT_NUMS;i+=2)
        {
                //vec[i - 1] = 1;
                vec[i + 1] = 1;
                if(vec[i]==0)
                {
                        for(j=i*i;j<=NUMS;j+=2*i)
                                vec[j]=1;
                }
        }
}
我还是多此一举了。会错意了。

紫色枫叶

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

                               
登录/注册后可看大图

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

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

#include <stdio.h>
#include <stdlib.h>

#define NUMS 100000
#define SQRT_NUMS 318

static int vec[NUMS+1];

/*
筛法求素数
(1)vec[i]==0则i为素数
(1)vec中下标为偶数的肯定不是素数
*/
void initTable();
//计算极品素数的个数
int count(int n);
void PrintAndCount(int n)
{
    /* for(int i = 2;i <= n; i++)
     {
                if(vec[i] == 0)  
                        printf("%d\t",i);
     }
     printf("\n");*/
        int result = 0;
        int priNumber = 2;
        for(int i = 3; i <= n; i++)
        {
                if(vec[i] == 0)
                {
                        if(i % 2 && vec[priNumber] == 0)
                        {
                                printf("%d\t", i);
                                result++;
                        }
                        priNumber++;
                }
        }
        printf("\n共有%d个极品素数\n", result);
}
int main(int argc, char **argv)
{
        int number;
        initTable();
    while(scanf("%d", &number) != EOF)
        {
                if(number == -1)
                        break;
                PrintAndCount(number);
        }
        system("pause");
        return 0;
}

void initTable()
{
        int i ,j, k;
                for(k = 4; k <= NUMS; k += 2)
                {
                        vec[k] = 1;
                }
        for(i = 3; i <= SQRT_NUMS; i += 2)
                {
                        if(vec[i] == 0)
                        {        
                                for(j = i * i; j <= NUMS; j += 2 * i)
                                        vec[j] = 1;
            }
        }
}

冬冬

紫色枫叶 发表于 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