-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathfoo2.java
More file actions
102 lines (92 loc) · 2.32 KB
/
Copy pathfoo2.java
File metadata and controls
102 lines (92 loc) · 2.32 KB
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
import java.math.BigInteger;
import java.util.Random;
public class PrimeEx {
/**
* @param args
*/
public static void main(String[] args) {
printTest(10, 4);
printTest(2, 2);
printTest(54161329, 4);
printTest(1882341361, 2);
printTest(36, 9);
System.out.println(isPrime(54161329) + " expect false");
System.out.println(isPrime(1882341361) + " expect true");
System.out.println(isPrime(2) + " expect true");
int numPrimes = 0;
Stopwatch s = new Stopwatch();
s.start();
for(int i = 2; i < 10000000; i++) {
if(isPrime(i)) {
numPrimes++;
}
}
s.stop();
System.out.println(numPrimes + " " + s);
s.start();
boolean[] primes = getPrimes(10000000);
int np = 0;
for(boolean b : primes)
if(b)
np++;
s.stop();
System.out.println(np + " " + s);
System.out.println(new BigInteger(1024, 10, new Random()));
}
public static boolean[] getPrimes(int max) {
boolean[] result = new boolean[max + 1];
for(int i = 2; i < result.length; i++)
result[i] = true;
final double LIMIT = Math.sqrt(max);
for(int i = 2; i <= LIMIT; i++) {
if(result[i]) {
// cross out all multiples;
int index = 2 * i;
while(index < result.length){
result[index] = false;
index += i;
}
}
}
return result;
}
public static void printTest(int num, int expectedFactors) {
Stopwatch st = new Stopwatch();
st.start();
int actualFactors = numFactors(num);
st.stop();
System.out.println("Testing " + num + " expect " + expectedFactors + ", " +
"actual " + actualFactors);
if(actualFactors == expectedFactors)
System.out.println("PASSED");
else
System.out.println("FAILED");
System.out.println(st.time());
}
// pre: num >= 2
public static boolean isPrime(int num) {
assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
final double LIMIT = Math.sqrt(num);
boolean isPrime = (num == 2) ? true : num % 2 != 0;
int div = 3;
while(div <= LIMIT && isPrime) {
isPrime = num % div != 0;
div += 2;
}
return isPrime;
}
// pre: num >= 2
public static int numFactors(int num) {
assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
int result = 0;
final double SQRT = Math.sqrt(num);
for(int i = 1; i < SQRT; i++) {
if(num % i == 0) {
result += 2;
}
}
if(num % SQRT == 0)
result++;
return result;
}
}