这几天学C++正好复习C,看到自己一开始写的程序,发现经常要写关于素数问题的程序下面是小弟刚学C时,书上的一个例子
题目:顺序输出3―100之间的所有素数
方法1：
#include<stdio.h>
main()
{int j,k,n,m=0;
for(n=3;n<=100;n++)
{
k=0; /*计数变量k清零*/
for(j=2;j<=n-1;j++)
{if(n%j==0) k++; /*如果n能被j整除，则k加1*/
}
if(k==0) {m++; printf("%5d",n)} /*如果n是素数，就输出*/
if(m%10==0) printf("\n"); /*每行输出10个素数*/
}
}
方法2：
#include<stdio.h>
#include<math.h>
main()
{int j,k,n,m=0;
for(n=3;n<=100;n++)
{
k=0; /*计数变量k清零*/
for(j=2;j<=sqrt(n);j++)
{if(n%j==0) k++; /*如果n能被j整除，则k加1*/
}
if(k==0) {m++; printf("%5",n);} /*如果n是素数，就输出n*/
if(m%10==0) printf("\n"); /*每行输出10个素数*/
}
}
下面这个是我从一本书上，根据意思改编的
题目：在主函数输入一个整数，输出是否是素数
#include<stdio.h>
#include<math.h>
main()
{int a,c;
printf("input a number");
scanf("%d",&a);
c=primef(a);
if(c) printf("%d is prime",a);
else printf("%d is not prime",a);
}
int primef(int x)
{int prime=5, gap=4;
if(x%2==0) return 0;
if(x%3==0) return 0;
while(prime<=sqrt(x))
{if(x%prime==0) return 0;
gap=6-gap; /*从5开始素数的规律是7（5+2），11（7+4），13（11+2）.........如此下去*/
prime+=gap;
}
return 1;
}
现在有个问题有没有能够更快的求出素数的方法？（我的想法就是减少for的循环次数）
----------------解决方案--------------------------------------------------------
Eratosthenes筛法
创建一个数组，以下面的方式将某些位置以1标记：从位置2开始，将所有2的倍数的位置
标记为1，然后对2之后的素数3进行同样的操作这样就可以找到3之后未被标记的5，
然后再将所有5的倍数记1，如此重复便可以找到数组中的所有素数。
没有被标志的数就是素数.复杂度O(n*(1+1/2+1/3+...1/n))
----------------解决方案--------------------------------------------------------
不错是个方法,只是不知道还有没有更简单的方法了?
----------------解决方案--------------------------------------------------------
``还是不会｀｀｀哎｀｀菜｀
----------------解决方案--------------------------------------------------------