Question

求写C语言程序，急用！！！

输入一个整数，判断它是不是素数，输出结果。。。

Answer 1

最简单的就是i从2到sqrt(n)范围一个一个判断 看是否n%i==0，如果有一个等于0，那就不是素数，否则就是素数。
bool IsPrime(int n)
{
if (2 == n)
return true;
int i;
for (i = 2; i <= sqrt(n); ++i) {
if (0 == n % i)
return false;
}

return true;
}
int main()
{
int n;
scanf("%d",&n);
if(IsPrime(n))
{
printf("%d是素数",n);
}
else
printf("%d不是素数",n);

return 0;
}

0.210秒，用Miller-Ribin检验素数
在oj上是15ms
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

int a, b;

int mpow( int s, int t, int m )
{
long long f, p;
if ( t == 0 )
return 1;
f = mpow( s, t >> 1, m );
if ( t & 1 )
{
p = s * f * f;
return p % m;
}
p = f * f;
return p % m;
}

int Miller_Ribin( int s )
{
int i, p;
for ( i = 0; i < 3; i++ )
{
p = rand()% ( s - 2 ) + 2;
if ( mpow( p, s - 1, s ) != 1 )
break;
}
return i == 3;
}

void work( int c )
{
int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;
if ( c == 1 )
{
if ( a <= 3 && b >= 3 )
printf("3\n");
if ( a <= 5 && b >= 5 )
printf("5\n");
if ( a <= 7 && b >= 7 )
printf("7\n");
return ;
}
for ( i = 0; i < p; i++ )
s *= 10;
for ( i = 1; i < 10; i += 2 )
{
for ( j = 0; j < s; j++ )
{
r = i * s + j;
t1 = j / 10;
t2 = p - 1;
while ( t2 )
{
r = r * 10 + ( t1 % 10 );
t1 /= 10;
t2--;
}
r = r * 10 + i;
if ( r < a )
continue;
if ( r > b )
return ;
if ( Miller_Ribin( r ) )
printf("%d\n", r);
}
}
}

int main( )
{
int s, e;
srand( time( NULL ) );
int i, p, c;
// scanf("%d%d", &a, &b);
a = 3; b = 1000000000;
p = 1;
c = 0;
while ( p < a )
{
c++;
p *= 10;
}
p /= 10;
while ( p < b )
{
if ( c == 2 )
printf("11\n");
if ( c & 1 )
work( c );
c++;
p *= 10;
}
printf("force program runs %.3lfs\n", clock( ) / (double)

追问

没明白，不过看起来很高深的样子。。判断素数要写这么长的程序呀

Answer 2

#include <math.h>
void isPrime(int n)
{
    int i,flag=1;;
    for(i=2;i<sqrt(n);i++)
        if(n%i==0) {printf("%d不是素数",n);flag=0;break;}
    if(flag==1)
        printf("%d是素数",n);
        
}

追问

都对哦，只能给最早的那个了

Answer 3

# include <stdio.h>
# include <math.h>
void main ()
{int m,i,k;
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)break;
if(i>k)printf("%d is prime number\n",m);
else printf("%d is not a prime numbeir\n",m);
system("pause");
}
还好来的及时

追问

你太牛B了，这么快