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

c++求任意两个数之间的所有素数~

【解题思路】本题的重点在如何判断一个数是否素数。判断素数的唯一标准就是能不能被除了1和本身之外的其它数整除，可以通过循环来判断，比如要判断27是否素数，可以用一个循环，从2开始到26逐个检测，看27能否被其中某个数整除，如果能就不是素数，否则就是素数。判断一个数是否被另一个数整除可以用取余运算符%，比如：a%b==0(就是a除以b的余数等于0)，就可以判定a可以被b整除。针对本题，为了使代码更简洁，可以专门写个判断一个数是否素数的函数，然后在主函数中调用就可以很容易实现求任意两个数之间的所有素数的要求。具体代码如下：【程序代码】#include //控制台操作头文件#include //数学函数头文件 int SS(int a) //质数判断函数(质数返回1,否则0){if(a<2) return 0; //小于2的数都不是质数,返回0 if(a==2) return 1; //2是特殊的质数 int i,n=(int)sqrt(a); //n是除数,开方可以减少检测个数 for(i=2;i<=n;i++) //逐个检测能不能被整除 if(a%i==0) return 0; //如果能被整除说明不是质数, 返回0; return 1;} //检测完了还没可以被整除的数,返回1 int main() //主函数{int i,a,b; //循环变量和任意两个数 printf("请输入起点："); //显示提示信息 scanf("%d",&a); //输入起点数值 printf("请输入终点："); //显示提示信息 scanf("%d",&b); //输入终点数值 printf("%d-%d之间的素质有:",a,b); //显示提示信息 for(i=a;i<=b;i++) //用循环逐个找出[a-b]之间的素数 if(SS(i)) printf("%d ",i);//如果是素数则输出 printf("
"); //换行 system("PAUSE"); //屏幕暂停,以便看到显示结果 return 0;} //结束程序【运行结果】本程序在 DEV C++上运行通过,截图如下:

zs函数错了。比如当x=33时，i<sqrt(33)的结果是i<5，i的取值就是2、3、4；那么，33%2时k=1，33%3时k=0，33%4时k又=1，结果最后得数是k=1，33成质数了，而33是合数！

首先，你说尽可能时间最小，那么我就认为你的空间复杂度无所谓乱了：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判断而已。

筛法求解素数，千万级只需要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;
}

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;
}

#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;
}

---

元坝区18363322418： 求任意两数之间素数个数(尽可能是时间最小且用C或C++),O(∩ - ∩)O谢谢~~ - ？
薄董百合： #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; }

元坝区18363322418： C语言编程求100—1000内的素数个数及和? - ？
薄董百合： #include <stdio.h> #include<math.h> #define M 100 #define N 1000 void Nprime(int m, int n); int prime(int k); int main() {Nprime(M,N); } void Nprime(int m, int n) {int i,flag=0,count=0,sum=0; for(i=m;i<=n;i++){if(prime(i)){count++;sum+=i;if(...

元坝区18363322418： c++求任意两个数之间的所有素数 - ？
薄董百合： 我的程序源代码截图如下:结果截屏如下;(两个整数是我随便输入的,你也可以改动)

元坝区18363322418： 用c语言求任意两个数之间的素数 - ？
薄董百合： 帮你写了一个,希望对你有帮助!!!/* 获取给定范围的素数 */ #include<stdio.h> int get_s(int n) /* 自定义取素数函数 */ {int a,pd=0;if(n>2)while(pd==0){for(a=2;a<n;a++){if(n%a==0){n++;continue;}}pd=1;}else n=2;return n; } int main(...

元坝区18363322418： c语言 统计输入两个数字之间素数个数并输出素数 - ？
薄董百合： 例: #include<stdio.h> voidmain() { inti,j,a,b; intc[100],count; count=0; do/*让输入的数a小于数b*/ scanf(＂%d%d＂,&a,&b); while(a>b); for(i=a;i<=b;i++)/*判断a.b之间的素数*/ {for(j=2;j<i;j++) if(i%j==0)break; if(i==j)c[count++]=i;/*如果是素数,最...

元坝区18363322418： 编写程序,求任意两个整数之间所有的素数.注意输入的两个整数谁大谁小是任意的. - ？
薄董百合： 不知道你要求的是什么语言,我用vf简单写了一下.input '请输入第一个数值:' to inp_a input '请输入第二个数值:' to inp_b*** *好长时间没用过input命令了,这里好像应该加入判断或转换程序段.以确保两个变量为数值型. ***?'正在计算中...

元坝区18363322418： c语言编写求两个数之间的数素？
薄董百合： #include <iostream> #include <cmath> using namespace std; bool IsPrime(int n) { for(int i=2,m=1; i<=sqrt(n); i++) if(!(m=n%i)) return false; return true; } void main() { int high, low; cout<<＂Input the limits(from low to high):＂<<endl; cin>>low>>high; ...

元坝区18363322418： pascal问题:输入任意两个自然数,求这两个数之间素数的个数. - ？
薄董百合： String.prototype.sub = function (n) { var r = /[^\x00-\xff]/g; if (this.replace(r, ＂mm＂).length <= n) return this; // n = n - 3;var m = Math.floor(n / 2); for (var i = m; i < this.length; i++) { if (this.substr(0, i).replace(r, ＂mm＂).length >= n) { return this.substr(0, i); }

元坝区18363322418： 编写一个c语言程序,任意输入两个数,可求出这两个数之间的所有回文素数 - ？
薄董百合： #include<stdio.h> int main(void) { int a,b; printf(＂请输入两个数:＂); scanf(＂%d%d＂,&a,&b); if(a>b) printf(＂最大的数为%d:\n＂,a); else printf(＂最大的数为%d:\n＂,b); }

元坝区18363322418： 编写程序,求任意两个整数之间所有素数.注意输入的两个整数谁大谁小是任意的. - ？
薄董百合： #include void main() { int m,n,a,k,i,t; scanf(＂%d%d＂, if(m>n) {t=m...