判断一个数是否为素数常见的四种方法
本文是我学习C语言过程中总结的四种判断素数的方法,使用的编译器为VS2022,作为初学者,代码有问题的地方欢迎大家指出
·
方法1:通过素数的定义判断
#include<stdio.h>
int isPrime(int i) {
int ret = 1;
int k;
for (k = 2; k < i - 1; k++) {
if (i % k == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(void) {
int a;
scanf_s("%d", &a);
if (isPrime(a) == 1) {
printf("%d是素数", a);
}
else {
printf("%d不是素数", a);
}
return 0;
}
方法2:已知1和除了2之外的偶数都不是素数
#include<stdio.h>
int isPrime(int x) {
int ret = 1;
int i;
if (x == 1 || x % 2 == 0 && x != 2) {
ret = 0;
}
for(i=3;i<x;i+=2){
if (x % i == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(void) {
int a;
scanf_s("%d", &a);
if (isPrime(a) == 1) {
printf("%d是素数", a);
}
else {
printf("%d不是素数", a);
}
return 0;
}
方法3:判断能否被已知的素数整除,已知prime[0]=2为第一个素数
#include<stdio.h>
//判断是否能被已知的素数整除
int isPrime(int x,int knownPrimes[],int numberofKnownPrimes) {
int ret = 1;
int i;
for (i = 0; i < numberofKnownPrimes; i++) {
if (x % knownPrimes[i] == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(void) {
const int number = 10;
int prime[10] = { 2 };
int count = 1;
int i = 3;
while (count < number) {
if (isPrime(i, prime, count)) {
prime[count++] = i;
}
i++;
}
for (i = 0; i < number; i++) {
printf("%d", prime[i]);
if ((i + 1) % 5) printf("\t");
else printf("\n");
}
return 0;
}
方法4:构造n以内(不含)的素数表
#include<stdio.h>
int main(void) {
const int maxNumber = 25;
int isPrime[25];
int i;
int x;
for (i = 0; i < maxNumber; i++) {
isPrime[i] = 1;
}
for (x = 2; x < maxNumber; x++) {
if (isPrime[x]) {
for (i = 2; i * x < maxNumber; i++) {
isPrime[i * x] = 0;
}
}
}
for (i = 2; i < maxNumber; i++) {
if (isPrime[i]) {
printf("%d\t", i);
}
}
printf("\n");
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)