质数,埃氏筛和欧拉筛(线性筛)"/>
筛选质数,埃氏筛和欧拉筛(线性筛)
求len之内的所有的素数
除了比较常用的开根号的求法,还有两种更好的方法,埃氏筛和线性筛。其中埃氏筛更好理解,而线性筛(欧拉筛)不好理解但是更快。
埃氏筛
#include <bits/stdc++.h>using namespace std;int main()
{int len = 100;vector<int> primes;bool isPrime[len+2];memset(isPrime, 1, len);for (int i = 2; i <= len; ++i){if (isPrime[i]){primes.push_back(i);for (int j = i*i; j <= len; j += i)isPrime[j] = false;}}for (vector<int>::iterator iter = primes.begin(); iter != primes.end(); ++iter)cout<<*iter<<" ";cout<<endl;
}
结果为:
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
讲解:
vector<int> primes
用于放置质数,isPrime
用于判断是否是质数,初始全为true
,也就是全是质数。之后设置把2和3
放进primes
里面。- 然后
i
从2
开始,遍历到len
,如果i
是质数,就放进primes
里,同时假如i
是质数,那么所有i
的倍数,肯定就不是质数了。所以2*i、3*i、4*i……
都不是质数。所以我们就可以不断将这些数的isPrime
设置为false
。 - 但是我们的循环是从
i*i
开始的,这是因为2*i、3*i到(i-1)*i
的所有合数,肯定会在之前就被设置为false
了。直观上看确实是,比如3*3是9,8会在4*2时被判断为合数,5*5是25,24会在8*3时被判断为合数。 - 具体证明不会,可以看这个。
欧拉筛(线性筛)
埃氏筛会有重复的情况,比如说40吧,在判断到2时,202是40,判断40是合数,在判断到5时,85=40,也判断40是合数,所以20就被判断了两次。这就有了欧拉筛。
#include <bits/stdc++.h>using namespace std;int main()
{int len = 100;vector<int> primes;bool isPrime[len+2];memset(isPrime, 1, len);for (int i = 2; i <= len; ++i){if (isPrime[i] == true)primes.push_back(i);for (int j = 0; j < primes.size(); ++j){if (i * primes[j] > len)break;isPrime[i * primes[j]] = false;if (i % primes[j] == 0)break;}}for (vector<int>::iterator iter = primes.begin(); iter != primes.end(); ++iter)cout<<*iter<<" ";cout<<endl;
}
vector<int> primes
用于放置质数,isPrime
用于判断是否是质数,初始全为true
,也就是全是质数。之后设置把2和3
放进primes
里面。- 然后
i
从2
开始,遍历到len
,如果i
是质数,就放进primes
里。同时,我们对现在判断好的所有质数primes[j]
,开始遍历,那么i*primes[j]
肯定就不是质数了,设置其isPrime
为false
。 - 但是在遍历
primes[j]
的时候,如果i % primes[j] == 0
,那么就不用再看接下来的i*primes[j+1]、i*primes[j+2]……
了,直接break
。这是因为如果i / primes[j] = m
,那么i = m * primes[j]
,那么i*primes[j+1] = m * primes[j] * primes[j+1] = (m*primes[j+1])*primes[j] = n*primes[j]
,也就是说这个数会在i*primes[j+1]
的时候被判断,也会在n*primes[j]
的时候被判断,其中n
是肯定大于i
的,因为i*primes[j+1] = n*primes[j]
,但是primes[j+1] > primes[j]
。那我们就等到当i
遍历到n
时,再去把i*primes[j+1]
这个数给判断成合数。 - 我们可以把每次筛出来的合数打印出来:
i is 3, primes[j] is 2, multi is 6
i is 3, primes[j] is 3, multi is 9
i is 4, primes[j] is 2, multi is 8
i is 5, primes[j] is 2, multi is 10
i is 5, primes[j] is 3, multi is 15
i is 5, primes[j] is 5, multi is 25
i is 6, primes[j] is 2, multi is 12
i is 7, primes[j] is 2, multi is 14
i is 7, primes[j] is 3, multi is 21
i is 7, primes[j] is 5, multi is 35
i is 7, primes[j] is 7, multi is 49
i is 8, primes[j] is 2, multi is 16
i is 9, primes[j] is 2, multi is 18
i is 9, primes[j] is 3, multi is 27
i is 10, primes[j] is 2, multi is 20
i is 11, primes[j] is 2, multi is 22
i is 11, primes[j] is 3, multi is 33
i is 11, primes[j] is 5, multi is 55
i is 11, primes[j] is 7, multi is 77
i is 12, primes[j] is 2, multi is 24
i is 13, primes[j] is 2, multi is 26
i is 13, primes[j] is 3, multi is 39
i is 13, primes[j] is 5, multi is 65
i is 13, primes[j] is 7, multi is 91
i is 14, primes[j] is 2, multi is 28
i is 15, primes[j] is 2, multi is 30
i is 15, primes[j] is 3, multi is 45
i is 16, primes[j] is 2, multi is 32
i is 17, primes[j] is 2, multi is 34
i is 17, primes[j] is 3, multi is 51
i is 17, primes[j] is 5, multi is 85
i is 18, primes[j] is 2, multi is 36
i is 19, primes[j] is 2, multi is 38
i is 19, primes[j] is 3, multi is 57
i is 19, primes[j] is 5, multi is 95
i is 20, primes[j] is 2, multi is 40
i is 21, primes[j] is 2, multi is 42
i is 21, primes[j] is 3, multi is 63
i is 22, primes[j] is 2, multi is 44
i is 23, primes[j] is 2, multi is 46
i is 23, primes[j] is 3, multi is 69
i is 24, primes[j] is 2, multi is 48
i is 25, primes[j] is 2, multi is 50
i is 25, primes[j] is 3, multi is 75
i is 26, primes[j] is 2, multi is 52
i is 27, primes[j] is 2, multi is 54
i is 27, primes[j] is 3, multi is 81
i is 28, primes[j] is 2, multi is 56
i is 29, primes[j] is 2, multi is 58
i is 29, primes[j] is 3, multi is 87
i is 30, primes[j] is 2, multi is 60
i is 31, primes[j] is 2, multi is 62
i is 31, primes[j] is 3, multi is 93
i is 32, primes[j] is 2, multi is 64
i is 33, primes[j] is 2, multi is 66
i is 33, primes[j] is 3, multi is 99
i is 34, primes[j] is 2, multi is 68
i is 35, primes[j] is 2, multi is 70
i is 36, primes[j] is 2, multi is 72
i is 37, primes[j] is 2, multi is 74
i is 38, primes[j] is 2, multi is 76
i is 39, primes[j] is 2, multi is 78
i is 40, primes[j] is 2, multi is 80
i is 41, primes[j] is 2, multi is 82
i is 42, primes[j] is 2, multi is 84
i is 43, primes[j] is 2, multi is 86
i is 44, primes[j] is 2, multi is 88
i is 45, primes[j] is 2, multi is 90
i is 46, primes[j] is 2, multi is 92
i is 47, primes[j] is 2, multi is 94
i is 48, primes[j] is 2, multi is 96
i is 49, primes[j] is 2, multi is 98
i is 50, primes[j] is 2, multi is 100
每个合数都只被筛了一次
总结
- 两个方法都是先假设所有数是质数,然后从里面筛出来合数。
- 埃氏筛是每次得到一个质数时,就对该质数的所有倍数筛除,因为他们肯定是合数。
- 欧拉筛是每次
i
从2到n
判断其是否是质数时,就对现在确定的所有质数k
遍历,把i*k
筛掉。 - 但是欧拉筛会在必要的时候
break
,保证每次筛掉的和数i*k
,质数k
都是最小的那个质数。比如20可以等于4*5
,也可以是10*2
,在这里i
分别是4和10
,质数k
分别是5和2
,我们会在10*2
这里将20筛掉,而是在4*5
这里,因为2
是最小的那个质数。
更多推荐
筛选质数,埃氏筛和欧拉筛(线性筛)
发布评论