1. /* programming with prime numbers */
2.
4. import java.util.BitSet;
5. import java.math.BigInteger;
6. import java.lang.Exception;
7. import java.lang.Boolean;
8. import java.util.Random;
9. import java.util.Collections;
10.
11. class Main {
12.
13. public static LinkedList primes(int n)
14. {
15. if (n < 2)
16. {
17. throw new IllegalArgumentException("must be greater than one");
18. }
19.
20. int m = (n-1) / 2;
21. BitSet b = new BitSet(m);
22. b.set(0, b.size(), true);
23.
24. int i = 0;
25. int p = 3;
28.
29. while (p * p < n)
30. {
31. if (b.get(i))
32. {
34. int j = 2*i*i + 6*i + 3;
35. while (j < m)
36. {
37. b.clear(j);
38. j = j + 2*i + 3;
39. }
40. }
41. i += 1; p += 2;
42. }
43.
44. while (i < m)
45. {
46. if (b.get(i))
47. {
49. }
50. i += 1; p += 2;
51. }
52.
53. return ps;
54. }
55.
56. public static Boolean tdPrime(BigInteger n)
57. {
58. BigInteger two = BigInteger.valueOf(2);
59.
60. if (n.compareTo(two) < 0)
61. {
62. throw new IllegalArgumentException("must be greater than one");
63. }
64.
65. if (n.mod(two).equals(BigInteger.ZERO))
66. {
67. return n.equals(two);
68. }
69.
70. BigInteger d = BigInteger.valueOf(3);
71.
72. while (d.multiply(d).compareTo(n) <= 0)
73. {
74. if (n.mod(d).equals(BigInteger.ZERO))
75. {
76. return false;
77. }
79. }
80.
81. return true;
82. }
83.
84. public static LinkedList tdFactors(BigInteger n)
85. {
86. BigInteger two = BigInteger.valueOf(2);
88.
89. if (n.compareTo(two) < 0)
90. {
91. throw new IllegalArgumentException("must be greater than one");
92. }
93.
94. while (n.mod(two).equals(BigInteger.ZERO))
95. {
97. n = n.divide(two);
98. }
99.
100. if (n.compareTo(BigInteger.ONE) > 0)
101. {
102. BigInteger f = BigInteger.valueOf(3);
103. while (f.multiply(f).compareTo(n) <= 0)
104. {
105. if (n.mod(f).equals(BigInteger.ZERO))
106. {
108. n = n.divide(f);
109. }
110. else
111. {
113. }
114. }
116. }
117.
118. return fs;
119. }
120.
121. private static Boolean isSpsp(BigInteger n, BigInteger a)
122. {
123. BigInteger two = BigInteger.valueOf(2);
124. BigInteger n1 = n.subtract(BigInteger.ONE);
125. BigInteger d = n1;
126. int s = 0;
127.
128. while (d.mod(two).equals(BigInteger.ZERO))
129. {
130. d = d.divide(two);
131. s += 1;
132. }
133.
134. BigInteger t = a.modPow(d, n);
135.
136. if (t.equals(BigInteger.ONE) || t.equals(n1))
137. {
138. return true;
139. }
140.
141. while (--s > 0)
142. {
143. t = t.multiply(t).mod(n);
144. if (t.equals(n1))
145. {
146. return true;
147. }
148. }
149.
150. return false;
151. }
152.
153. public static Boolean isPrime(BigInteger n)
154. {
155. Random r = new Random();
156. BigInteger two = BigInteger.valueOf(2);
157. BigInteger n3 = n.subtract(BigInteger.valueOf(3));
158. int k = 25;
159.
160. if (n.compareTo(two) < 0)
161. {
162. return false;
163. }
164.
165. if (n.mod(two).equals(BigInteger.ZERO))
166. {
167. return n.equals(two);
168. }
169.
170. while (k > 0)
171. {
172. a = new BigInteger(n.bitLength(), r).add(two);
173. while (a.compareTo(n) >= 0)
174. {
175. a = new BigInteger(n.bitLength(), r).add(two);
176. }
177.
178. if (! isSpsp(n, a))
179. {
180. return false;
181. }
182.
183. k -= 1;
184. }
185.
186. return true;
187. }
188.
189. private static BigInteger rhoFactor(BigInteger n, BigInteger c)
190. {
191. BigInteger t = BigInteger.valueOf(2);
192. BigInteger h = BigInteger.valueOf(2);
193.
194. while (d.equals(BigInteger.ONE))
195. {
199. d = t.subtract(h).gcd(n);
200. }
201.
202. if (d.equals(n)) /* cycle */
203. {
205. }
206. else if (isPrime(d)) /* success */
207. {
208. return d;
209. }
210. else /* found composite factor */
211. {
213. }
214. }
215.
216. public static LinkedList rhoFactors(BigInteger n)
217. {
218. BigInteger two = BigInteger.valueOf(2);
220.
221. if (n.compareTo(two) < 0)
222. {
223. return fs;
224. }
225.
226. while (n.mod(two).equals(BigInteger.ZERO))
227. {
228. n = n.divide(two);
230. }
231.
232. if (n.equals(BigInteger.ONE))
233. {
234. return fs;
235. }
236.
237. while (! n.isProbablePrime(25))
238. {
239. f = rhoFactor(n, BigInteger.ONE);
240. n = n.divide(f);
242. }
243.
245. Collections.sort(fs);
246. return fs;
247. }
248.
249. public static void main (String[] args)
250. {
251. System.out.println(primes(100));
252. System.out.println(primes(1000000).size());
253. System.out.println(tdPrime(new BigInteger("600851475143")));
254. System.out.println(tdFactors(new BigInteger("600851475143")));
255. System.out.println(isPrime(new BigInteger("600851475143")));
256. System.out.println(isPrime(new BigInteger("2305843009213693951")));
257. System.out.println(rhoFactors(new BigInteger("600851475143")));
258. }
259.
260. }
Success #stdin #stdout 0.11s 246080KB
stdin
Standard input is empty
stdout
[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]
78498
false
[71, 839, 1471, 6857]
false
true
[71, 839, 1471, 6857]