h******r
发帖数: 201 | 1 楼主只会这个基本方法，虽然work,但速度根本达不到要求。请教大牛，如何提高速度？
int nPrime(int N)
{
int nP=1;
for (int i=3; i<=N; i+=2)
{
bool yy=true;
for (int j=1; j
{
if(i%j==0)
{
yy=false;
break;
}
}
if(yy==true) nP++;
}
return nP;
} |
D*******a
发帖数: 3688 | 2 j loop only need to use known primes up to sqrt(i)
度？
【在 h******r 的大作中提到】
: 楼主只会这个基本方法，虽然work,但速度根本达不到要求。请教大牛，如何提高速度？
: int nPrime(int N)
: {
: int nP=1;
: for (int i=3; i<=N; i+=2)
: {
: bool yy=true;
: for (int j=1; j: {
: if(i%j==0)
|
S*A
发帖数: 7142 | 3
度？
你的程序 j=1 是错的，任何数字可以被 1 整除。
如果可以用内存换时间的话可以快很多：
你的改正过的程序，
time ./a.out
9592
real 0m0.426s
user 0m0.424s
sys 0m0.000s
我的：
time ./a.out
9592
real 0m0.001s
user 0m0.000s
sys 0m0.000s
N = 1000000 貌似快了 400 倍？
更大的数更快。
int nPrime(int N)
{
int n= N/2 - !(N & 1);
char *buffer;
int i,j;
int count =1;
if (N<3)
return N == 2;
buffer = calloc(1,n);
if (!buffer)
return -1;
for (i=1; i
int step;
if (buffer[i])
continue;
count++;
step = i*2 + 1;
for (j=i + step; j
buffer[j]= 1;
}
free(buffer);
return count;
}
【在 h******r 的大作中提到】
: 楼主只会这个基本方法，虽然work,但速度根本达不到要求。请教大牛，如何提高速度？
: int nPrime(int N)
: {
: int nP=1;
: for (int i=3; i<=N; i+=2)
: {
: bool yy=true;
: for (int j=1; j: {
: if(i%j==0)
|
m******u
发帖数: 12400 | |
a*f
发帖数: 1790 | 5 re
找到一个质数放到hashtable里面，只检查是否被里面的质数群整除
【在 D*******a 的大作中提到】
: j loop only need to use known primes up to sqrt(i)
:
: 度？
|
b********0
发帖数: 62 | 6 如果空间没要求的话 直接开一个队列从2开始
每次取出队列头 然后把这个的倍数全部标记为删除
队列头如果是删除的就跳过 这样队列头肯定是质数
就是3楼的做法 没仔细看...
度？
【在 h******r 的大作中提到】
: 楼主只会这个基本方法，虽然work,但速度根本达不到要求。请教大牛，如何提高速度？
: int nPrime(int N)
: {
: int nP=1;
: for (int i=3; i<=N; i+=2)
: {
: bool yy=true;
: for (int j=1; j: {
: if(i%j==0)
|
S*A
发帖数: 7142 | 7 因为跳过偶数，只考虑奇数的因子。2 已经被放到 NP 里面了。
当然这有个 bug 就是如果 N=1 的话返回 1 是不对的，应该是 0.
【在 m******u 的大作中提到】
: 为什么j的叠加是2.
|
S*A
发帖数: 7142 | 8 思路类似，但是我的做法更加优化一些。
我直接跳过了偶数，这样数组的大小比你的算法减少
一半，循环也减少一半。当然数组下标的处理就要
仔细考虑这个下标折半的边界条件。
【在 b********0 的大作中提到】
: 如果空间没要求的话 直接开一个队列从2开始
: 每次取出队列头 然后把这个的倍数全部标记为删除
: 队列头如果是删除的就跳过 这样队列头肯定是质数
: 就是3楼的做法 没仔细看...
:
: 度？
|
