-
Notifications
You must be signed in to change notification settings - Fork 77
/
prime.cpp
93 lines (86 loc) · 2.48 KB
/
prime.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
vector<int> primes;
vector<bool> marked;
void sieve(int n) {
marked = vector<bool>(n + 1, false);
int sqrtN = sqrt(n);
for(int i = 3; i <= sqrtN; i += 2) {
if(!marked[i]) {
for(int j = i; j <= n; j += (i << 1)) {
marked[j] = true;
}
marked[i] = false;
}
}
if(n >= 2) primes.push_back(2);
for(int i = 3; i <= n; i += 2) {
if(!marked[i]) {
primes.push_back(i);
}
}
}
/***
calculate primes between L and R where 1 <= L <= R <= INT_MAX and 0 <= R - L <= 10^5
1. generate primes using sieve upto sqrt(INT_MAX)
2. using those primes calculate segmented sieve/primes between ranges
***/
void segmentedSieve(unsigned int left, unsigned int right) {
int sqrtR = sqrt(right);
marked = vector<bool>(right - left + 1, false); // marked.resize(right - left + 1, false) don't work :(
for(int i = 1; i < primes.size() and primes[i] <= sqrtR; i++) {
// offset is equal or immediate larger prime of left
int offset = ((left + primes[i] - 1) / primes[i]) * primes[i];
for(int j = offset; j <= right; j += primes[i]) {
marked[j - left] = true;
}
if(offset == primes[i]) {
marked[offset - left] = false;
}
}
if(left <= 2 and 2 <= right) {
// prime => 2
}
for(int i = max(((left & 1) ? left : left + 1), 3u); i <= right; i += 2) {
if(!marked[i - left]) {
// prime => i
}
}
}
// prime factorization using sieve
// 45 = 3^2 * 5^1
void primeFactor(int x, vector<pair<int, int>>& factors) {
for(int i = 0; i < primes.size() and primes[i] <= x; i++) {
if(x % primes[i] == 0) {
int p = primes[i];
int freq = 0;
while(x % p == 0) {
freq++;
x /= p;
}
factors.push_back({p, freq});
}
}
}
// quick factorization without any preprocess
void primeFactor2(int x, vector<pair<int, int>>& factors) {
int sqrtX = sqrt(x);
if(x % 2 == 0) {
int p = 2;
int freq = 0;
while(x % p == 0) {
x /= p;
freq++;
}
factors.push_back({p, freq});
}
for(int i = 3; i <= sqrtX; i += 2) {
if(x % i == 0) {
int p = i;
int freq = 0;
while(x % p == 0) {
freq++;
x /= p;
}
factors.push_back({p, freq});
}
}
}