不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

求素数

楼主qingfeng81（）2005-04-25 23:40:43 在 C/C++ / C语言提问

从键盘随机输入十个数求其中有几个是素数，输出格式：There are 5 prime number.
新手求代码。
马上结贴。谢谢问题点数：100、回复次数：13Top

1 楼arrowcy（长弓手）回复于 2005-04-25 23:58:36 得分 23

int prime(int n)
{
int i;
for (i=2;i<=n/2;i++)
if(n%i==0)
return 1;
return 0;
}Top

2 楼arrowcy（长弓手）回复于 2005-04-26 00:00:17 得分 0

#include <stdio.h>
#include <stdlib.h>

main()
{
int n,i,t;
n=0;
for (i=0;i<10;i++)
{
scanf("%d",&t);
if(prime(t)) n++;
}
printf("%d\n",n);
}Top

3 楼arrowcy（长弓手）回复于 2005-04-26 00:00:44 得分 0

第二帖要调用第一帖的函数Top

4 楼flying_dancing（小混混-_-）回复于 2005-04-26 00:43:36 得分 0

void shushu(int a) //a是需要判断的数
{
for(int b=2;b<=sqrt(a);b++)
{
if(a%b==0){cout<<"不是"; break;}
}
}

Top

5 楼du51（郁郁思扬）回复于 2005-04-26 00:44:00 得分 40

#include<stdio.h>
#include<conio.h>
#include<math.h>
int prim(int a)
{
int i;
if(a<=1)return 0;
if(a==2)return 1;
if(a%2==0)return 0;
for(i=3;i<=sqrt(a);i+=2)
{
if(a%i==0)return 0;
}
return 1;
}
int main()
{
int a[10],i=0,count=0;
printf("INPUT your data\n");
while(i<10)scanf("%d",&a[i++]);
while(i>-1)if(prim(a[--i]))count++;
printf("There are %d prim",count);
getch();
}Top

6 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-04-26 10:08:33 得分 0

du51(郁郁思扬)的更标准些了,
又晚了的说Top

7 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-04-26 10:10:20 得分 1

100分呢,分我点啊Top

8 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2005-04-26 13:05:11 得分 1

upTop

9 楼xuzheng318（忧郁王子）回复于 2005-04-26 13:08:10 得分 10

#include <iostream.h>
#include <math.h>
#include <windows.h>

const unsigned default_n=4000000000;
const int maxlen=1000;

int primes[maxlen];
int len;
int sum;
unsigned int n;
int m=7;
int Q=1;
int phiQ=1;
int* v;

bool string2int(unsigned int& n,char* s);
void init(void);
unsigned int phi(unsigned int x,int a);

void main(void){
char number_string[80];
unsigned int time;

cout<<"calc pi(n)\n";
cout<<"n(default = "<<default_n<<") = ";
cin.get(number_string,80);
if(!string2int(n,number_string))n=default_n;

time=GetTickCount();
init();
int num=(int)phi(n,len)-sum+len-1;
time=GetTickCount()-time;
GlobalFree(v);
cout<<"pi(n)="<<num<<"("<<time<<"ms)\n";
cout<<"press any key to continue...";
cin.get();
cin.get();
}

void init(void){
int max;
int sqrt_max;
bool* mark;
int i,j;
int len2,len3;
int s;

max=(int)(pow(1.0*n,2.0/3.0)+1.5);
sqrt_max=(int)(sqrt(max)+0.5);
mark=(bool*)GlobalAlloc(GMEM_FIXED|GMEM_ZEROINIT,max);

for(i=2;i<sqrt_max;++i){
if(!mark[i]){
j=i*i;
while(j<max){
mark[j]=true;
j+=i;
}
}
}

for(len=0,i=2;(unsigned)i*i*i<=n;++i){
if(!mark[i])primes[++len]=i;
}

for(j=max-1,sum=0,s=0,len2=len;(unsigned)i*i<=n;++i){
if(!mark[i]){
++len2;
while((unsigned)i*j>n){
if(!mark[j])++s;
--j;
}
sum+=s;
}
}

for(len3=len2;i<max;++i){
if(!mark[i])++len3;
}

sum=(len2-len)*len3-sum;
sum+=len*(len-1)/2-len2*(len2-1)/2;

if(m>len)m=len;
for(i=1;i<=m;++i){
Q*=primes[i];
phiQ*=primes[i]-1;
}

v=(int*)GlobalAlloc(GMEM_FIXED,Q*sizeof(int));
for(i=0;i<Q;++i)v[i]=i;
for(i=1;i<=m;++i){
for(j=Q-1;j>=0;--j){
v[j]-=v[j/primes[i]];
}
}

GlobalFree(mark);
}

bool string2int(unsigned int& n,char* s){
unsigned int val=0;
for(int i=0;s[i];++i){
if(s[i]>'9'||s[i]<'0')return false;
val*=10;
val+=s[i]-'0';
if(val>default_n)return false;
}
n=val;
return true;
}

unsigned int phi(unsigned int x,int a){
if(a==m){
return (x/Q)*phiQ+v[x%Q];
}
if(x<(unsigned)primes[a]){
return 1;
}
return phi(x,a-1)-phi(x/primes[a],a-1);
}Top

10 楼ycom__net（一恒）回复于 2005-04-26 16:37:08 得分 10

#define size 100
void main(){
bool p[size];
cout<<size<<"内的质数有:2";
int i;
for(i=3;i<size;i+=2)p[i]=true;
for(i=3;i<size;i+=2)
if(p[i]){
cout<<" "<<i;
for(int j=i+i+i;j<size;j+=i+i)p[j]=false;
}
}

一个判素数的算法，

输出个数就不用些了把
直接调用
Top

11 楼pcboyxhy（-273.15℃）回复于 2005-04-26 16:40:13 得分 5

int prime(int n)
{
int i;
for (i=2;i<=n/2;i++) //到sqrt(n) 就ok了就算把n/2单独提取出来,也会快很多
if(n%i==0)
return 1;
return 0;
}
Top

12 楼llf_hust（）回复于 2005-04-26 16:51:51 得分 5

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int Prime(int n)
{
int i;
int j = sqrt(n);
for (i = 2; i <= j; i+=2)
if (n%i == 0)
return 0;
return 1;
}

main()
{
int n,i,t;
n=0;
for (i=0;i<10;i++)
{
scanf("%d",&t);
if(Prime(t)) n++;
}
printf("%d\n",n);
getche();
}Top

13 楼hunanlion（湖南雄狮）回复于 2005-04-26 16:59:32 得分 5

int prime(int n)
{
int i,j=0;
for (i=2;i<=n/2;i++)
if(n%i==0)
j++;
return j;
return 0;
}

Top

求素数