-
Notifications
You must be signed in to change notification settings - Fork 515
/
Copy pathprimes.java
148 lines (127 loc) · 5.89 KB
/
primes.java
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import java.util.*;
public class ch5_06_primes {
int _sieve_size;
boolean[] bs; // 10^7 should be enough for most cases
List<Integer> primes = new ArrayList<Integer>(); // compact list of primes in form of vector<int>
// first part
void sieve(int upperbound) { // create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs = new boolean[_sieve_size];
Arrays.fill(bs,true); // set all bits to 1
bs[0] = bs[1] = false; // except index 0 and 1
for (long i = 2; i < _sieve_size; i++) if (bs[(int)i]) {
// cross out multiples of i starting from i * i!
for (long j = i * i; j < _sieve_size; j += i) bs[(int)j] = false;
primes.add((int)i); // also add this vector containing list of primes
} } // call this method in main method
boolean isPrime(long N) { // a good enough deterministic prime tester
if (N < _sieve_size) return bs[(int)N]; // O(1) for small primes
for (int i = 0; i < primes.size(); i++)
if (N % primes.get(i) == 0) return false;
return true; // it takes longer time if N is a large prime!
} // note: only work for N <= (last prime in vi "primes")^2
// second part
List<Integer> primeFactors(long N) { // remember: vi is vector of integers, long is long long
List<Integer> factors = new ArrayList<Integer>(); // vi `primes' (generated by sieve) is optional
int PF_idx = 0;
long PF = primes.get(PF_idx); // using PF = 2, 3, 4, ..., is also ok
while (N != 1 && (PF * PF <= N)) { // stop at sqrt(N), but N can get smaller
while (N % PF == 0) { N /= PF; factors.add((int)PF); } // remove this PF
PF = primes.get(++PF_idx); // only consider primes!
}
if (N != 1) factors.add((int)N); // special case if N is actually a prime
return factors; // if pf exceeds 32-bit integer, you have to change vi
}
// third part
long numPF(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = 0;
while (N != 1 && (PF * PF <= N)) {
while (N % PF == 0) { N /= PF; ans++; }
PF = primes.get(++PF_idx);
}
if (N != 1) ans++;
return ans;
}
long numDiffPF(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = 0;
while (N != 1 && (PF * PF <= N)) {
if (N % PF == 0) ans++; // count this pf only once
while (N % PF == 0) N /= PF;
PF = primes.get(++PF_idx);
}
if (N != 1) ans++;
return ans;
}
long sumPF(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = 0;
while (N != 1 && (PF * PF <= N)) {
while (N % PF == 0) { N /= PF; ans += PF; }
PF = primes.get(++PF_idx);
}
if (N != 1) ans += N;
return ans;
}
long numDiv(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = 1; // start from ans = 1
while (N != 1 && (PF * PF <= N)) {
long power = 0; // count the power
while (N % PF == 0) { N /= PF; power++; }
ans *= (power + 1); // according to the formula
PF = primes.get(++PF_idx);
}
if (N != 1) ans *= 2; // (last factor has pow = 1, we add 1 to it)
return ans;
}
long sumDiv(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = 1; // start from ans = 1
while (N != 1 && (PF * PF <= N)) {
long power = 0;
while (N % PF == 0) { N /= PF; power++; }
ans *= ((long)Math.pow((double)PF, power + 1.0) - 1) / (PF - 1); // formula
PF = primes.get(++PF_idx);
}
if (N != 1) ans *= ((long)Math.pow((double)N, 2.0) - 1) / (N - 1); // last one
return ans;
}
long EulerPhi(long N) {
int PF_idx = 0;
long PF = primes.get(PF_idx), ans = N; // start from ans = N
while (N != 1 && (PF * PF <= N)) {
if (N % PF == 0) ans -= ans / PF; // only count unique factor
while (N % PF == 0) N /= PF;
PF = primes.get(++PF_idx);
}
if (N != 1) ans -= ans / N; // last factor
return ans;
}
void run(){
// first part: the Sieve of Eratosthenes
sieve(10000000); // can go up to 10^7 (need few seconds)
System.out.printf("%b\n", isPrime(2147483647)); // 10-digits prime
System.out.printf("%b\n", isPrime(136117223861L)); // not a prime, 104729*1299709
// second part: prime factors
List<Integer> res = primeFactors(2147483647); // slowest, 2147483647 is a prime
for (int i : res) System.out.printf("> %d\n", i);
res = primeFactors(136117223861L); // slow, 2 large pfactors 104729*1299709
for (int i : res) System.out.printf("# %d\n", i);
res = primeFactors(142391208960L); // faster, 2^10*3^4*5*7^4*11*13
for (int i : res) System.out.printf("! %d\n", i);
//res = primeFactors((long)(1010189899 * 1010189899)); // "error"
//for (vi::iterator i = res.begin(); i != res.end(); i++) System.out.printf("^ %d\n", *i);
// third part: prime factors variants
System.out.printf("numPF(%d) = %d\n", 50, numPF(50)); // 2^1 * 5^2 => 3
System.out.printf("numDiffPF(%d) = %d\n", 50, numDiffPF(50)); // 2^1 * 5^2 => 2
System.out.printf("sumPF(%d) = %d\n", 50, sumPF(50)); // 2^1 * 5^2 => 2 + 5 + 5 = 12
System.out.printf("numDiv(%d) = %d\n", 50, numDiv(50)); // 1, 2, 5, 10, 25, 50, 6 divisors
System.out.printf("sumDiv(%d) = %d\n", 50, sumDiv(50)); // 1 + 2 + 5 + 10 + 25 + 50 = 93
System.out.printf("EulerPhi(%d) = %d\n", 50, EulerPhi(50)); // 20 integers < 50 are relatively prime with 50
}
public static void main(String[] args){
new ch5_06_primes().run();
}
}