Question

求任意两数之间素数个数（尽可能是时间最小且用C或C++),O(∩_∩)O谢谢~~

Answer 1

首先，你说尽可能时间最小，那么我就认为你的空间复杂度无所谓乱了：D
因此用下面的算法：
1，先说说算法原理
(1)定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个"素数"因子d.
(2)素数定理: ln(x)-3/2 < x/PI(x) < ln(x)-1/2, 当x >= 67时.，其中PI(x)为x范围你素数的个数，
，由(1)有，2^32范围内的素数判断需要判断PI(2^16)个素数即可
由(2)，可以估算2^16范围类的素数个数即PI(2^16) 大致为6138－6834个，实测为6542个。
因此，要求时间尽可能小，如下：
定义常量数组，2^16内所有素数，可以编程产生输出到文件，再拷进程序，因为这段为常量，时间复杂度为O(1)....hoho
const static int primes[] =
{
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,
593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
...
65521, 65537
};
或者你不想弄这个常量数组，那么用下面的产生primes数组

// 构造素数序列primes[]
其中的num=2^16，这个也是程序开始一次运行即可，时间复杂度可认为是常数
void makePrimes(int primes[], int num)
{
int i, j, cnt;

primes[0] = 2;
primes[1] = 3;

for(i = 5, cnt = 2; cnt < num; i += 2)
{
int flag = true;
for(j = 1; primes[j]*primes[j] <= i; ++j)
{
if(i%primes[j] == 0)
{
flag = false; break;
}
}
if(flag) primes[cnt++] = i;
}
}

//判断是否素数用如下算法，原理是利用定理(1)
//其中primes[]即上面定义的常量数组，这个算法时间复杂度为O(PI(sqrt(n)))，其中PI上面说了
bool isPrime(const int primes[], int n)
{
if(n < 2) return false;

for(int i = 0; primes[i]*primes[i] <= n; ++i)
if(n%primes[i] == 0) return false;

return true;
}

最后的[a,b]范围内的素数个数就不用详述了吧？一个循环，每个用isPrime判断而已。

Answer 2

筛法求解素数，千万级只需要1秒左右。
#include <vcl.h>
#pragma hdrstop
#include <math.h>
#include <stdio.h>

//---------------------------------------------------------------------------

#pragma argsused

int main(int argc, char* argv[])
{
long MINNUM,MAXNUM;
bool *Store;
unsigned long start;
printf("Take the count of Prime number!\n");
while(1)
{
printf("***********************************");
printf("\nPlease Input start number: ");
scanf("%d",&MINNUM);
printf("Please Input end number: ");
scanf("%d",&MAXNUM);
if(MINNUM<0 || MAXNUM<0 || MINNUM>MAXNUM)
{
printf("Your input number is invalid!!!");
break;
}

start = GetTickCount();
Store = new bool[MAXNUM+1];
memset(Store,1,sizeof(bool)*(MAXNUM+1));
memset(Store,0,2);
long Temp = sqrt(MAXNUM);
for(int i=2 ; i<=Temp ;i++)
{
if(Store[i])
for(int j=i ; (j*i)<=MAXNUM ; j++)
Store[j*i] = false;
}
int count = 0;
for(int i=MINNUM ; i<=MAXNUM ; i++)
{
if(Store[i])
{
count++;
//printf("%4d ",i);
}
}
printf("Between number [%d] and number[%d]:\nprime number: %d\n",MINNUM,MAXNUM,count);
printf("Use time:%d\n",GetTickCount()-start);
delete []Store;
}

return 0;
}

Answer 3

C语言 包括输入的两个数
#include<stdio.h>
int main()
{
int i,j,a,b,tj=0;
scanf("%d%d",&a,&b);

for(i=a;i<=b;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0)
break;
}
if(j==i)
tj++;
}

printf("%d\n",tj);
return 0;
}

C++ 不包括输入的两个数
#include<iostream>
using namespace std;
bool f(int x)
{
int i;
for(i=2;i<x;i++)if(x%i==0)break;
if(i==x)return true;
else return false;
}
void main()
{
int a,b,s=0,i;
cin>>a>>b;
for(i=a+1;i<b;i++)if(f(i))s++;
cout<<s<<endl;
}

Answer 4

#include<iostream>
using namespace std;
bool f(int x)
{
int i;
for(i=2;i<x;i++)if(x%i==0)break;
if(i==x)return true;
else return false;
}
void main()
{
int a,b,s=0,i;
cin>>a>>b;
for(i=a+1;i<b;i++)if(f(i))s++;
cout<<s<<endl;
}