算法-极品素数-参与有奖,数据结构与算法,技术交流,鱼C论坛

冬冬发表于 2011-7-23 10:40:46

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

本帖最后由冬冬于 2011-7-23 16:50 编辑

极品素数：如果一组素数从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

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

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

1.LZ题目出错了，9=3*3,所以9不是素数，所以9不是极品素数
2.贴我的代码#include<stdio.h>
#define NUMS 100000
#define SQRT_NUMS 316

static int vec;

/*
筛法求素数
(1)vec==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==0){
for(j=i*i;j<=NUMS;j+=2*i)
vec=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==0) {
++priNumber;
if( priNumber%2 && vec == 0 ){
result++;
}
}
}
return result;
}

冬冬发表于 2011-7-23 16:49:17

仰望天上的光发表于 2011-7-23 13:13 static/image/common/back.gif
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:17

冬冬发表于 2011-7-23 19:18:00

elyric 发表于 2011-7-23 17:41 static/image/common/back.gif

结果错误

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

我的程序有问题，改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==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;

/*
筛法求素数
(1)vec==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==0){
                     for(j=i*i;j<=NUMS;j+=2*i)
                           vec=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==0) {
                     ++priNumber;
                     if( priNumber%2 && vec == 0 ){
                        result++;
                     }
            }
   }
   return result;
}

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

仰望天上的光发表于 2011-7-23 22:25 static/image/common/back.gif
我的程序有问题，改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;
/*

筛法求素数

(1)vec==0则i为素数

(1)vec中下标为偶数的肯定不是素数

*/

void initTable();

//计算极品素数的个数

int count(int n);

void PrintTable()
{
for(int i=2;i<=100;i++)
{
         if(vec==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==0){

                     for(j=i*i;j<=NUMS;j+=2*i)

                           vec=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==0) {

                     ++priNumber;

                     if( priNumber%2 && vec == 0 ){

                        result++;

                     }

            }

   }

   return result;

}

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

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

elyric 发表于 2011-7-23 22:58:34

紫色枫叶 发表于 2011-7-24 00:29:40

本帖最后由紫色枫叶于 2011-7-24 12:23 编辑

仰望天上的光发表于 2011-7-23 22:25 static/image/common/back.gif
我的程序有问题，改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 = 1;
            vec = 1;
            if(vec==0)
            {
                     for(j=i*i;j<=NUMS;j+=2*i)
                           vec=1;
            }
   }
}
我还是多此一举了。会错意了。

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

冬冬发表于 2011-7-23 22:44 static/image/common/back.gif
我一直纳闷的是，我给你的代码添加了一个PrintTable函数，打印了2 - 100之间的素数，如下图。但是这个 ...

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

#define NUMS 100000
#define SQRT_NUMS 318

static int vec;

/*
筛法求素数
(1)vec==0则i为素数
(1)vec中下标为偶数的肯定不是素数
*/
void initTable();
//计算极品素数的个数
int count(int n);
void PrintAndCount(int n)
{
/* for(int i = 2;i <= n; i++)
{
if(vec == 0)
printf("%d\t",i);
}
printf("\n");*/
int result = 0;
int priNumber = 2;
for(int i = 3; i <= n; i++)
{
if(vec == 0)
{
if(i % 2 && vec == 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 = 1;
}
   for(i = 3; i <= SQRT_NUMS; i += 2)
{
if(vec == 0)
{
for(j = i * i; j <= NUMS; j += 2 * i)
vec = 1;
         }
   }
}

冬冬发表于 2011-7-24 17:09:50

紫色枫叶发表于 2011-7-24 16:36 static/image/common/back.gif
我在你修改仰望天上的光的基础,又进行了一点调整,可以统计极品素数的个数并输出预期的极品素数。

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

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

楼主，，，那个2好像也是极品素数吧{:5_107:}

冬冬发表于 2011-7-24 21:53:04

断点发表于 2011-7-24 19:21 static/image/common/back.gif
楼主，，，那个2好像也是极品素数吧

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

Be_envious 发表于 2011-7-24 23:50:12

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

tcwz 发表于 2011-7-25 19:05:45

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

redguy 发表于 2011-8-12 02:39:04

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

785131460 发表于 2011-10-13 00:31:46

#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;
}

丿夏夜灬彬刂 发表于 2012-6-16 01:05:06

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

梦幻羽羽 发表于 2012-7-27 09:59:23

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

页: [1]

鱼C论坛's Archiver

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