求素数，有什么好的算法。执行效率较高的。

老谭的书上有啊~

老谭的练习有答案吗?

#include<stdio.h>
void main()
{
int n,k=2;
printf("请输入一个正整数");
scanf("%d",&n);
printf("%d=",n);
while(n>=k)
{
while(n%k!=0)
{
k++;
}
printf("*%d",k);
n/=k;
}
}

请教：这是判断素数的方法吗？
类似与分解，感觉，
还不是质因数分解，好象

#include <math.h>
bool isSuShu(long n)
{
long K = (long)sqrt(n) ;
long num ;
for(num = 2 ; num < K ; num++)
{
if(n%num == 0)
{
return false ;// 不是素数
}
}
return true ;// 是素数

}

调试调试吧

效率为 sqrt(n) ;

测试k是否为素数。可以用k去除m，m为奇数，故m+=2,且m小于sqrt（k）。
if(k%m!=0),就说明k是素数，这个效率高些。

http://hi.baidu.com/pcrazyc

我在博客中第一遍浅淡素数有说明,可以参考一下

本人又优化了一下,程序如下:

[CODE]#include<iostream>
#include<time.h>
#define N 100000000
bool a[N];
using namespace std;
void prime(unsigned long n) //用筛法将不是素数的值置0
{
unsigned long i,j;
a[0]=1; //2是唯一的偶素数,另作打算
for(i=3;i<=n;i+=2) //将大于2小于或等于n的奇数
a[i/2]=1;
for(i=3;i<=n/3;i+=2) //只要考虑小于n/3的就可以了,因为乘以2就是偶数,至少也是乘以3,
大于n/3的就不用判断
{
if(a[i/2])
for(j=i*3;j<=n;j+=2*i) //j的奇数倍的数全部筛选出去
a[j/2]=0;
}
}
int main()
{
unsigned long n,sum,i;
clock_t start,finish;
while(scanf("%d",&n))
{
start=clock();
prime(n);
sum=1;
for(i=3;i<=n;i+=2)
if(a[i/2])
sum++;
cout<<"the number of the prime less than n is "<<sum<<endl;
finish=clock();
cout<<"the promgram expends "<<(double)(finish-start)<<"ms"<<endl;
}
return 0;
}[/CODE]

详情参考:http://hi.baidu.com/pcrazyc

输出1亿内的素数个数只需要5秒左右