素数函数isPrime()
(素数:指在大于1的自然数中,除了1和它自身外,不能被其他自然数整除的数。)
方法一
int isPrime(int x) {int ret = 1;int i;if (x == 1) ret = 0;for (i = 2;i < x;i++) {if (x % i == 0) {ret = 0;break;}}return ret;}
方法二
(去掉偶数从3到x-1,每次加2)
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;}
(无须到x-1,到sqrt(x)——x的平方根就行了)
sqrt() 头文件 #include<math.h>
int isPrime(int x) {int ret = 1;int i;if (x == 1||(x%2==0&&x!=2)) ret = 0;for (i = 3;i < sqrt(x);i+=2) {if (x % i == 0) {ret = 0;break;}}return ret;} 另外,用数组构造素数表
方法一
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;}//该函数用于判断x能否被已知的素数数组中的元素除尽 int main(void) {const int number = 100;int prime[number] = { 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;}
方法二
#include <stdio.h>int main(void) {const int maxNumber = 25;int isPrime[maxNumber];int i, x;//先将数组全赋值为turefor (i = 0;i < maxNumber;x++) {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;}