怎么样求N以下所有素数
GMP有没有自带这么一个函数：给定一个整数N，输出N以下所有的素数N。matlab里面就有类似的函数
如果GMP没有的话，这个函数要怎么写？
其实我的目的是想随机得到N以下的一个素数，如果有上面的函数的话，我只要从N里面选一个就行了。
关于随机得到N以下的一个素数，我自己是这么写的
gmp_randinit_default(state); 设置随机初始状态
do
{
mpz_urandomm(r, state, N); 得到N以下随机一个数，赋给r
mpz_nextprime(r, r); 求得r的下一次素数，赋给r
}
while(mpz_cmp(r, N)>=0); 如果r>N，返回循环重新生成
如果只要得到一个随机素数的话，感觉还可以。不过我是用到很多个随机素数，所以感觉每次都要这么生成，效率不高。
求牛人帮我解答问题！ //计算2^31 以内素数个数, 打印每个结果需自己写点代码
//
#include <math.h>
#include <stdio.h>
#include <memory.h>
#include <time.h>
#define ST 7
#define MOVE 4
#define BLOCKSIZE (510510 * 4) // 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510
#define MAXM ((BLOCKSIZE >> MOVE) + 1)
#define SET_BIT(a, n)a |= (1 << (n & 7))
typedef unsigned int uint;
typedef unsigned char uchar;
static uint Prime;
static uchar NumBit0;
static uchar BaseTpl;
static const uint MAXN = (-1u / 2);
static int sieve( )
{
int primes = 1;
const uint maxp = (1 << 16) + 1000;
for (uint p = 3; p < maxp; p += 2) {
if (0 == (BaseTpl & (1 << (p / 2 & 7)))) {
Prime = p;
for (uint i = p * p / 2; i < maxp / 2; i += p)
SET_BIT(BaseTpl, i);
}
}
return primes;
}
static void initBit( )
{
memset(BaseTpl, 0, sizeof(BaseTpl));
for (int k = 1; k < ST; k++)
for (int p = Prime / 2; p < sizeof(BaseTpl) * 8; p += Prime)
SET_BIT(BaseTpl, p);
for (int i = 1; i < sizeof(NumBit0) / sizeof(NumBit0); i++)
NumBit0 = NumBit0 + (i & 1);
for (int j = 0; j < sizeof(NumBit0) / sizeof(NumBit0); j++)
NumBit0 = 8 - NumBit0;
}
static void inline
crossOutFactorMod6(uchar bitarray[], const uint start,
const uint leng, uint factor)
{
uint s2, s1 = factor - start % factor;
s1 += factor - factor * (s1 % 2);
if (start <= factor)
s1 = factor * factor;
const char skip[] = {0, 2, 1, 1, 0, 1};
const char mrid = ((start + s1) / factor) % 6 - 1;
s1 = s1 / 2 + skip * factor;
s2 = s1 + skip * factor;
for (factor += 2 * factor; s2 <= leng / 2; ) {
SET_BIT(bitarray, s1); s1 += factor; //6k + 1
SET_BIT(bitarray, s2); s2 += factor; //6k + 5
}
if (s1 <= leng / 2)
SET_BIT(bitarray, s1);;
}
static int inline setSieveTpl(uchar bitarray[], uint start, int leng)
{
const int offset = start % BLOCKSIZE;
memcpy(bitarray, BaseTpl + (offset >> MOVE), (leng >> MOVE) + 2);
if (start < 32)
*((short*)bitarray) = 0x3461; //0x 0011 0100 0110 0001
bitarray |= (1 << (offset % 16 / 2)) - 1;
leng += offset % 16;
*((uint*)bitarray + (leng >> 6)) |= ~((1u << (leng / 2 & 31)) - 1);
return offset % 16;
}
static int segmentedSieve(uint start, int leng)
{
uchar bitarray;
const int offset = setSieveTpl(bitarray, start, leng);
start -= offset, leng += offset;
const int maxp = (int)sqrt((double)start + leng) + 1;
for (int i = ST, p = Prime; p < maxp; p = Prime[++i])
crossOutFactorMod6(bitarray, start, leng, p);
int primes = 0;
for (int k = 0; k <= leng >> MOVE; k++)
primes += NumBit0];
return primes;
}
int countPrimes(uint start, uint stop)
{
int primes = 0;
if (start <= 2 && stop >= 2)
primes = 1;
const int blocksize = 63 << 14;
if (start + blocksize > stop)
return primes + segmentedSieve(start, stop - start + 1);
primes += segmentedSieve(start, blocksize - start % blocksize);
for (uint i = start / blocksize + 1; i < stop / blocksize; i++)
primes += segmentedSieve(i * blocksize, blocksize);
primes += segmentedSieve(stop - stop % blocksize, stop % blocksize + 1);
return primes;
}
int main(int argc, char* argv[])
{
uint start = 0, stop = MAXN;
clock_t tstart = clock();
sieve();
initBit();
int primeCnt = countPrimes(0, MAXN);
const char *ouput = "PI(%u, %u) = %d, time use %u ms\n";
printf(ouput, start, stop, primeCnt, clock() - tstart);
while (scanf("%u %u", &start, &stop) == 2 && stop >= start) {
tstart = clock();
primeCnt = countPrimes(start, stop);
printf(ouput, start, stop, primeCnt, clock() - tstart);
}
return 0;
}
//PI = 105097565, time use 1592 ms
// 这个程序能生成2^2048内的素数吗？
我发现你没有用到GMP大数库啊！ LZ头像好热阿 题目是求N以下的所有素数。3#又问"这个程序能生成2^2048内的素数吗?", 如果我没有理解错的话，你是想要2^2048以内的所有素数，这实在是一个"天才"的的想法，让我来算一下，需要多少硬盘才能存下这么多素数。
1. 以最朴素的存储方法，存储1个2048bit的素数需要2048/8=256B
2. 根据素数定理可知，2^2048以内素数个数为 2^2048/ln(2^2048),约等于2^2038个素数。需要2^2038×256B=2^2046B=2^2006TB.
3. 假设硬盘的容量为2TB(当前主流硬盘容量),并假设技术足够进步，使得这样的硬盘的质量仅为1个电子的质量(约为10^-30千克),则所需的硬盘总质量为 2^2006TB/2TB×10^-30千克=3.67×10^573千克。
4. 3.67×10^573千克 是个什么概念呢？我们知道地球的质量约为6×10^24千克。太阳的质量约为2×10^30千克，宇宙1.53×10^54千克(来源http://wenwen.soso.com/z/q136056252.htm)，那个3.67×10^573千克比宇宙的质量实在是大的太多太多太多了。 退一步，即使求$2^64$以内的所有素数，所需的存储容量也相当可观。
$2^64$以内的所有素数大约有$4×10^17$个，按每个素数需要8字节，需要$4×10^17×8=3.2×10^18B=3.2×10^6TB$,以每块硬盘2T，每块硬盘重量0.5公斤计算，硬盘的总重量仍达$3.2×10^6"TB"//(2"TB")xx0.5KG=800$吨。 3# fly
在我看来2^60 已经是天文数字， 楼主对数字大小还没有概念， 还是认为
现在的计算机是以光速运行。 即便是能生成2^60以内素数，
你要这么大范围数以内素数do what？循序扫描一遍什么也不干也，要等个十年八年的。 唉呀，我本来就是要找很大的素数，达到密码上要求的安全。
2^60从密码上来说太小了，微不足道，不够安全，而且如果是2^60随便找个软件就行了，要不然还用GMP干嘛！
5楼6楼的东西我看得头晕，本来我的N是2^2048的，怎么到你那么变成了22048了，下次写的东西都不知你写什么，宇宙有1.53×1054千克（＝1吨）那么轻吗？你忽悠人啊！
还有啊，麻烦看一下一楼的内容，不要只是看标题嘛。 如果只要得到一个随机素数的话，感觉还可以。不过我是用到很多个随机素数，所以感觉每次都要这么生成，效率不高
大哥，这才是我真正想要滴，不能被理解，好郁闷啊 8# fly
严重怀疑你的浏览器不能显示Latext公式，请double check.