判断素数的五种方法
方法一
暴力法
int main()
{
int i=0;
for(i=100;i<200;i++)
{
int j=0;
int flag=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag==1)
{
printf("%d ",i);
}
}
return 0;
}
小优化一下
int main()
{
int i=0;
for(i=101;i<200;i+=2)//偶数不是素数所以i+=2
{
int j=0;
int flag=1;
for(j=2;j<=(int)sqrt(i);j++)//只需要判断2到根号n的数
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag==1)
{
printf("%d ",i);
}
}
return 0;
}
方法二：
六步进法判断素数
bool isPrime(int n) {
if (n <= 1) {
return false; // 小于等于1的数不是素数
}
if (n <= 3) {
return true; // 2和3是素数
}
if (n % 2 == 0 || n % 3 == 0) {
return false; // 能被2或3整除的数不是素数
}
int i;
for (i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false; // 如果能被i或i+2整除，则不是素数
}
}
return true; // 经过上述检查后，如果都不是，则为素数
}
六步进法判断素数的原理是基于素数的分布规律。对于大于等于5的自然数，素数一定出现在6的倍数的两侧，即6x和6x+1的位置上。如11和13，17和19。
大于等于5的质数一定和6的倍数相邻，具体表现为6x-1, 6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5, 6(x+1)等形式。在这些数中，6x+2、6x+3、6x+4等不是素数，因为它们可以被2或3整除。因此，判断一个大于等于5的数是否为素数时，只需检查其是否为6的倍数或其相邻的数即可。
方法三：
埃氏筛
void sieveOfEratosthenes(int n) {
// 创建一个布尔数组，初始时假设所有数都是素数
bool *prime = (bool *)malloc((n + 1) * sizeof(bool));
for (int i = 2; i <= n; i++) {
prime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
// 如果prime[p]未改变，则它是一个素数
if (prime[p] == true) {
// 更新所有p的倍数为非素数
for (int i = p * p; i <= n; i += p) {
prime[i] = false;
}
}
}
for (int p = 2; p <= n; p++) {
if (prime[p]) {
printf("%d ", p);
}
}
有个缺点就是只能聪从2开始筛选，不然筛选不全，不能直接给出某段区间的所用素数。
方法四：
线性筛：
int countPrime1(int n)
{
int* arr1 = calloc(n + 1, sizeof(int)); // 用于存放素数的数组
int* primes = calloc(n + 1, sizeof(int)); // 标记数组是否是素数
int prime_count = 0; // 记录素数的数量
for (int i = 2; i < n; i++)
{
if (primes[i] == 0)
{
primes[i] = 1; // i 是素数
arr1[prime_count++] = i; // 将素数 i 加入 arr1 数组
}
for (int j = 0; j < prime_count && i * arr1[j] < n; j++)
{
primes[i * arr1[j]] = -1; // i * arr1[j] 不是素数
if (i % arr1[j] == 0)
break; // 若 i 能整除 arr1[j]，则退出循环
}
}
// 释放内存
free(arr1);
free(primes);
return prime_count;
}
适用于小范围的素数查找，并且也只能从2开始筛选。
埃氏筛和线性筛的原理参考
原文地址：https://blog.csdn.net/2403_82759827/article/details/142833122
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！