判断素数（质数）的四种方法

2023-07-26 19:01| 来源: 网络整理| 查看: 265

普通解法根据素数的定义除了1和它本身没有其他的因数，就是素数，所以把数用从2~数本身-1的数字除于看看有没有被整除，如果没有被整除那么这个数就是质数。这个办法只适用于用于被判断数较小的情况。数字太大会非常慢。时间复杂度O(n) 样例代码（C++）

bool judgement_prime(int n) { for (int i = 2; i //根据需要开数组大小别开太小了 //标记下标数字是不是素数，false是素数true不是素数 bool* flag = new bool[128]; //记录素数 int* prime = new int[128]; //默认所有数字都是素数 fill(flag, flag + 128, false); flag[0] = flag[1] = true; //0，1不是素数 int cut = 0; //发现的素数个数 //筛选出0到n的所有素数并记录 for (int i = 2; i //标记下标数字是不是素数，false是素数true不是素数 bool* flag = new bool[128]; //记录素数 int* prime = new int[128]; //默认所有数字都是素数 fill(flag, flag + 128, false); flag[0] = flag[1] = true; //0，1不是素数 int cnt = 0; //发现的素数个数 //筛选出2到n的所有素数并记录 for (int i = 2; i //标记素数的倍数为不是素数 flag[i * prime[j]] = true; //保证每次值会在最小的质数因子对的时候进行筛选 if (i % prime[j] == 0) break; } } //prime数组里存着所有找到素数 //flag标记着下标是不是素数 //cut是发现的素数个数 //可以看情况进行利用 //例如判断n是不是素数直接 return !flag[n]; //因为false标记的素数所以返回时可取反返回 //这样是素数就true不是则false }

if(i % prime[j] == 0) break;这一步是关键，也是比较费解的。任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们要保证能找到的是有最小质因子的数对。当i是prime[j]的整数倍时，i*prime[j+1]肯定被筛过，跳出循环。因为如果 i % p r i m e [ j ] = 0 i \% prime[j] = 0 i%prime[j]=0那么就会存在一个x成立 p r i m e [ j ] × x = i prime[j] \times x = i prime[j]×x=i当然也肯定有个y能成立 p r i m e [ j + 1 ] × y = i prime[j+1] \times y = i prime[j+1]×y=i 因为prime[j] 一定小于prime[j+1]所以prime[j+1]已经不可能是i的最小质因子了，往后就没必要计算了。

练习题洛谷质数口袋洛谷质数口袋解析

【本文地址】

公司简介

联系我们