关于质数的有关问题
关于质数的问题
关于质数的问题,我的想法是:
把求得的质数放在一个数组内,再用待求数去除那个数组,
若不可除,则把它放入数组,再用下一个待求数去除那个数组,
以此循环下去.
这样行不?
若行,该如何编?
有什么方法是最有效的方法?
------解决方案--------------------
可行,在数量比较少时
------解决方案--------------------
楼主不是已经把算法都说出来了吗?
------解决方案--------------------
嗯,这个就是“素数筛选法”
速度是相对较快的哦!
我们先设保存整数0~N的数组为sieve[N+1],用“逐步求精”的方法来得出算法:
[定理1]若比素数P小的所有素数的倍数均已从sieve中删去,且P*P > N,则sieve = primes(2…N)。
其中:primes(2..N)表示2..N之间所有的素数。
------解决方案--------------------
关于质数的问题,我的想法是:
把求得的质数放在一个数组内,再用待求数去除那个数组,
若不可除,则把它放入数组,再用下一个待求数去除那个数组,
以此循环下去.
这样行不?
若行,该如何编?
有什么方法是最有效的方法?
------解决方案--------------------
可行,在数量比较少时
------解决方案--------------------
楼主不是已经把算法都说出来了吗?
------解决方案--------------------
嗯,这个就是“素数筛选法”
速度是相对较快的哦!
我们先设保存整数0~N的数组为sieve[N+1],用“逐步求精”的方法来得出算法:
[定理1]若比素数P小的所有素数的倍数均已从sieve中删去,且P*P > N,则sieve = primes(2…N)。
其中:primes(2..N)表示2..N之间所有的素数。
------解决方案--------------------
- C/C++ code
//上次写的 #include <stdio.h> #define N 200 int main() { int mark[N+1] = {0}; int i, j, k; for (i = 2; i-N-1; mark[i] = i + 1, i++); for (i = 2; i-N-1; mark[k] = N + 1, i = mark[i]) for (k = i, j = mark[i]; j-N-1; j = mark[j]) if (j%i) mark[k] = j, k = j; for (i = 2; i-N-1; printf("%d\t", i), i = mark[i]); return 0; }