判断整数N(N>2)是否为质数的编程

Question

如题所述

Answer 1

关于素数的判定
所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是，在一张纸上写上1到100全部整数，然后逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。

具体做法如下：
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> 用3去除它后面的各数，把3的倍数挖掉。
<4> 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1～50的素数，要一直进行到除数为47为止（事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n^2(根号n)，取其整数即可。例如对1～50，只需进行到将50^2作为除数即可。）

如上算法可表示为：
<1> 挖去1;
<2> 用刚才被挖去的数的下一个数p去除p后面各数，把p的倍数挖掉;
<3> 检查p是否小于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执行，否则就结束;
<4> 纸上剩下的数就是素数。

#include <stdio.h>
#include <math.h>

int main(void)
{
int i;
int j;
int a[101]; // 为直观表示，各元素与下标对应，0号元素不用

for (i = 1; i <= 100; i++) // 数组各元素赋值
a[i] = i;

for (i = 2; i < sqrt(100); i++) // 外循环使i作为除数
for (j = i + 1; j <= 100; j++) // 内循环检测除数i之后的数是否为i的倍数
{
if (a[i] != 0 && a[j] != 0) // 排除0值元素
if (a[j] % a[i] == 0)
a[j] = 0; // i后数若为i的倍数，刚将其置0(挖去)
}

int n = 0; // 对输出素数计数, 以控制换行显示

for (i = 2; i <= 100; i++) // 输出素数
{
if (a[i] != 0)
{
printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数)
n++;
}
if (n == 10)
{
printf("\n"); // 每行10个输出
n = 0;
}
}
printf("\n");

return 0;
}

运行结果(VC):

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

Answer 2

const int MCCNT=10; bool composite;

__int64 power(__int64 a,__int64 p ,__int64 n)
{

__int64 x,result;
if(p == 0) return 1;
else{
x=power(a,p/2,n);
result = (x*x)%n;
if(result==1 && (x!=1) && (x != (n-1)) ) composite = true;
if(p%2==1) result=(result*a)%n;
}
return result;
}

bool primeMC(__int64 n)
{
composite = false;
__int64 a,result;

for(int i=1;i<=MCCNT;i++)
{
a= ( (double) rand() / (double) RAND_MAX )*(n-3)+2;
result=power(a,n-1,n);
if(composite || (result !=1)) return false;
}
return true;

}

Answer 3

用N去除以1~根号N的整数部分，如果都不能整除，那就是质数