怎样求素数的判断

用C语言如何判断素数~

介绍三种使用C语言来判断素数的方法，以及用做素数表来判断找素数的方法。

什么都不说了，直接上代码
#include
bool isPrim(int num) {
for(int i = 2; i <= num/2; i++) {
if( num%i == 0) {
return false;
} else {
continue;
}
}
return true;
}
void main() {
int num, count;
printf("请输入查找素数的最大范围： ");
scanf("%d", &num);
for(int j = 2; j <= num; j++) {
if(isPrim(j)) {
if(count%10 ==0) {
printf("
");
}
printf("%6d ",j);
count++;
}
}
printf("
");
}

一、查<素数表>，看已知数是否为素数；
二、计算已知数A的平方根√A，分别用不超过√A的各个素数去试除A，如果所有不大于√A的素数都不能整除A，则A为素数；否则为合数。
例如，判断1867是否是素数，先算√1867≈43.2，然后分别计算1867除以43、41、37、31、29、23、……3、2等素数，都除不尽，则1867为素数。当然，1867不能被11、5、3、2整除是很容易判定的。

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。如13，只能被1和13整除。所以要判断a是否是素数，只要判断a能否被2到a-1之间的数整除，如果能则说明a能被1和a之外的数整除，即a不是素数；如果不能则说明a只能被1和a整除，即a是素数。
但是这样的判断方法做了很多无用功，假设b能整除a，c为商(即a=b*c)。则b和c的大少关系有两种：一种b,c中一大一小(又a=√a*√a,所以b,c中一个大于√a一个数小于√a)，另一种b=c(此时,√a=b=c)。故如果a能被大于√a的数整除则一定存在一个小于√a的数能整除a。所以只要判断2到√a的整数是否能整除a就行了。
例如求1000以内的素数：
#include <stdio.h>
#include <math.h>
void main()
{
int i,a,b;
for(a=2;a<=1000;a++)
{
b=sqrt(a);//求a的平方根
for(i=2;i<=b;i++)
if(a%i==0)
break;
if(i>b)//如果i>sqrt(a)则说明2到sqrt(a)之间没有数可以整除a，故a为素数
printf("%4d",a);
}

}

---

门源回族自治县17563776209： 求一个数怎样判断它是不是素数 - ？
温筠氨酪： 用辗转相除法,思路是:采用循环将这个数N从2开始除,一直除到N-1为止,其间若发现除尽,则跳出循环,认为它不是素数,若一直无法除尽,则判定其为素数 .

门源回族自治县17563776209： 如何判断一个数是素数 c++ - ？
温筠氨酪： 给你写个函数,你试试…… bool prime(int n){ if(n>2 && !(n&1) || n<2) return false; for(int i=3;i*i<=n;i+=2) if(!(n%i)) return false; return true; }

门源回族自治县17563776209： 急求判断素数的好方法 - ？
温筠氨酪： 如果楼主问的不是初学者的问题的话,建素数表可以逆用费尔马小定理,多试几个底,虽然有几率但是错误率很小的

门源回族自治县17563776209： 求素数的方法? - ？
温筠氨酪：[答案] 偶数首先排除,其次个位为5的也排除掉(肯定能被5整除),剩下个位为1,3,7,9的数字进行判断,用来作为因数尝试的数,个位也只能为1,3,7,9,而且不能大于被判断的数的平方根,似乎形成了一个递归,即要判断的数,只要测试能否被前面得到的...

门源回族自治县17563776209： C++几种常见的素数判断算法 - ？
温筠氨酪： int su(int a){//返回1为素数int i = 2;for(;i <= a/2;i ++){if(a % i == 0)return 0;}return 1; }

门源回族自治县17563776209： 求一个数的素数求一个数的是不是素数,这个素数是n,判断这个数能不能被被2~(n - 1)之间的数整除,还有一种说法是只需要判断n被2~根号n之间的整数除就... - ？
温筠氨酪：[答案] 如果2到√n都不能整除n 假设n有一个因数a,且a≠n 则还有一个因数是n/a 且a>√n 则n/a即n/a这和2到√n都不能整除n矛盾 所以假设的a不存在 所以n是素数

门源回族自治县17563776209： 判断质数(素数)的要求 - ？
温筠氨酪： 假设a=s*t, s,t≠1,不妨设s≤t 则a=s*t ≥ s*s = s² 则 s ≤ √a, 即如果一个数a不是质数,那么他分解得到的两个约数,必然有一个不大于√a 所以,只要确定2~√a之间没有a的约数,即不能被2~√a之间的数整除,那么a就是质数

门源回族自治县17563776209： 如何编写一个C语言程序判断一个数是否是素数? - ？
温筠氨酪： 1. 思路1: 判断一个整数m是否是素数,只需把m被 2 ~ m-1 之间的每一个整数去除,如果都不能被整除,那么m就是一个素数.代码如下: #include <stdio.h> int main(){ int a=0; // 素数的个数 int num=0; // 输入的整数 printf(＂输入一个整数...

门源回族自治县17563776209： 如何用筛选法求出100以内的素数 - ？
温筠氨酪： 先用可用枚举法得到1-100的自然数.然后拥循环结构把每个数进行判断,用这个数去除以从2开始到他本身减1(其实判断到这个数的二分之一即可).不能整除的输出来即可.

门源回族自治县17563776209： 求素数的判别的详细解释为什么说1.只须将n被2~n/2间的整数除2.只须被2~根号2(不会打根号)之间的整数除本人数学没天分,求详解, - ？
温筠氨酪：[答案] 如果n为合数,则可写成n=a*b(a和b是大于或等于2的整数) 则a,b,中的较小者必然小于或等于根号n(否则n=a*b>根号n*根号n=n) 所以若2到小于或等于根号n的数都不能整除n那么n就是素数