素数判断
嗨嗨害 第一篇题解来啦
- 素数判断
-
例题
【题目描述】
给出一个正整数n,输出1-n所有素数,用空格分开。
【输入样例】
100
【输出样例】
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
看到素数判断首先想到……
方法壹 普通(难度:1/10)
首先想到素数的性质
根据小学课本:素数(质数)是只有1和它本身两个因数的数叫做素数
因此 枚举大法就此出现!!!
我们想到从2枚举到他本身-1,只要出现一个因数,就立刻停止,判定为不是素数,我们定义一个函数,像这样:
bool/*返回值为布尔变量*/ is_prime(int x){ if (x <= 1) return false;//特殊判断,1不是素数 if (x == 2) return true;//特殊判断,too for (int i = 2; i <= x - 1; ++i){//从2枚举到x-1 if (x % i == 0){//如果能除尽(是因数) return false;//就返回FALSE(不是) } } return true;//三种情况都不是,就是素数 }但仔细想想就会发现:时间复杂度太高:O(n^2)
于是我们就都可以想到,因数是成对出现的,可以只枚举到n/2
改成:
bool is_prime(int x){ if (x <= 1) return false; if (x == 2) return true; for (int i = 2; i <= x / 2 /*优化*/; ++i){ if (x % i == 0){ return false; } } return true; }但,时间复杂度还是差不多,所以可以只枚举到√n
(至于为什么我不知道)bool is_prime(int x){ if (x <= 1) return false; if (x == 2) return true; //for (int i = 2; i <= sqrt(x)/*再优化*/; ++i){ //但是,众所众知平方根的计算效率是很慢的,不如乘法,SO for (int i = 2; i * i <= x; ++i){ if (x % i == 0){ return false; } } return true; }方法贰 埃氏筛(爱氏筛)(难度:5/10)
第二种方法:我们可以从1开始枚举到n把所有枚举数的倍数(合数)全部标记(删除)
注:此方法仅适用于一段范围内
#include<iostream> #include<cstdio> using namespace std; bool hash[1005] = {false};//建立一个标记数组 int ans[1005]; //储存结果 int main(){ int n,cnt = 0/*计数*/; cin >> n ; for (int i = 2; i <= n; ++i){ if (hash[i]) continue;//如果已被标记为合数,直接下一个 for (int j = i; j <= n / i; ++j){//枚举 hash[i * j] = true;//标记合数 } ans[cnt++] = i;//不是合数,加入素数组 } --cnt; cout << 2 << ' ' ;//特殊待遇 for (int i = 1; i <= cnt; ++i){ cout << ans[i] << ' ' ; }//输出 return 0; }好!现在已经完成了埃氏筛!时间复杂度:O(NlnlnN)
——管他咋来的但,他是完美的吗?
NO!
方法 叁 线性筛(
O啦筛欧拉筛)(难度:8/10)闪亮登场!
首先,我们考虑:埃氏筛其实有重复啊!
SO,怎样去掉重复呢?
设我们已经找到了素数数组prime,从2枚举到n,只要用每个素数prime[i]都乘上i,就是所得合数,标记,那个可怜的合数也只被他最小的素因数去除了
但如果发现i可以除尽该素数,那马上停止,因为继续乘的话后面也一定是该素数的倍数,可有效防止重复!
#include<iostream> #include<cstdio> using namespace std; bool hash[1005];//建立一个标记数组 int prime[1005]; //储存结果 int main(){ int n,cnt = 1; prime[1] = 2; cin >> n ; for (int i = 2; i <= n; ++i){ if (hash[i] == 0) prime[++cnt] = i;//... for (int j = 1; j <= cnt && i * prime[j] <= n/*防止超界*/; ++j){//继续枚举 hash[prime[j] * i] = true; if (i % prime[j] == 0) break;//避免重复 } } for (int i = 1; i <= cnt; ++i){ cout << prime[i] << ' ' ; } return 0; }时间复杂度:O(n)左右