isPrime()函数:判断素数，构造素数表

落日映苍穹つ 2022-11-03 11:44 227阅读 0赞

## 素数函数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;
    	//先将数组全赋值为ture
    	for (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;
    }