Skip to content

Instantly share code, notes, and snippets.

@hephaestus9

hephaestus9/SieveOfAtkin-Java.java

Last active June 13, 2017 14:50
Show Gist options
  • Save hephaestus9/6a47e429f3f8c91d87bd to your computer and use it in GitHub Desktop.
Save hephaestus9/6a47e429f3f8c91d87bd to your computer and use it in GitHub Desktop.
Download ZIP
Sieve Of Atkin - Java
Raw
SieveOfAtkin-Java.java
/*
* The function of this class is to find all prime numbers in range given by the user.
*
* This homework assignment requires several references:
* http://www.avajava.com/tutorials/lessons/how-do-i-use-threads-join-method.html
* http://stackoverflow.com/questions/1428786/best-way-to-find-a-prime-number
* http://web.mit.edu/16.070/www/lecture/big_o.pdf
* http://en.wikipedia.org/wiki/Sieve_of_Atkin
* http://stackoverflow.com/questions/3790142/java-equivalent-of-pythons-rangeint-int
* http://stackoverflow.com/questions/17279519/removing-items-from-list-in-java
*
* If the person that posted to stackoverflow is accurate then the sieve of atkin grows at a considerably slower rate
* compared to the sieve of eratosthenes
*/
package hw4_9_20_14;
import java.util.*;
public class SieveOfAtkin {
public static void main(String[] args) throws InterruptedException{
Scanner userInput = new Scanner( System.in );
System.out.println("Please enter an integer for the start of the range: ");
int start = userInput.nextInt();
System.out.println("Please enter an integer for the stop of the range: ");
int stop = userInput.nextInt();
userInput.close();
int results[] = candidates(start, stop);
List<Integer> primes = sieve(results, start, stop);
System.out.println("Number of primes returned: " + primes.size());
System.out.println(primes);
test(primes, start, stop);
System.out.println("Finished.");
}
public static int[] candidates(int start, int stop) throws InterruptedException{
int[] result = new int[((stop + 1) - start)];
int[] numbers = new int[((stop + 1) - start)];
int[] xy = new int[(int) ((Math.sqrt(stop) + 1))];
int[] n1 = new int[((stop + 1) - start)];
int[] n2 = new int[((stop + 1) - start)];
int[] n3 = new int[((stop + 1) - start)];
int[] primeList1 = new int[n1.length];
int[] primeList2 = new int[n2.length];
int[] primeList3 = new int[n3.length];
int ct1 = 0;
int ct2 = 0;
int ct3 = 0;
//System.out.println(Math.sqrt(stop));
for(int i=0;i<(stop + 1) - start;i++){
numbers[i] = start+i;
}
for(int i = 1; i < (int) (Math.sqrt(stop) + 1); i ++){
xy[i] = i;
//System.out.println(i);
}
for(int i =0; i < numbers.length; i++){
int num = numbers[i] % 60;
//1, 13, 17, 29, 37, 41, 49, or 53
if (num == 1 || num == 13 || num == 17 || num == 29 || num == 37 || num == 41 || num == 49 || num == 53){
n1[ct1] = numbers[i];
//System.out.println(numbers[i]);
ct1++;
}
//7, 19, 31, or 43
if (num == 7 || num == 19 || num == 31 || num == 43){
n2[ct2] = numbers[i];
//System.out.println(numbers[i]);
ct2++;
}
//11, 23, 47, or 59,
if (num == 11 || num == 23 || num == 47 || num == 59){
n3[ct3] = numbers[i];
//System.out.println(numbers[i]);
ct3++;
}
}
class quad1 implements Runnable {
public quad1(int[] xy, int[] n1, int stop, int[] primeList1) {
//n ← 4x²+y²
//if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):
// is_prime(n) ← ¬is_prime(n)
for (int p = 0; p < n1.length; p++){
for (int i = 0; i < xy.length; i ++){
for (int j = 0; j < xy.length; j ++){
//System.out.println(n1[p] * 1.0 + ", " + ((4 * Math.pow(i, 2)) + Math.pow(j, 2)));
if(n1[p] == (int) ((4 * Math.pow(i, 2)) + Math.pow(j, 2))){
//System.out.println(n1[p] + ", " + (int) ((4 * Math.pow(i, 2)) + Math.pow(j, 2)));
if (n1[p] <= stop + 1 && (n1[p] % 12 == 1 || n1[p] % 12 == 5)){
primeList1[p] = n1[p];
//System.out.println(n1[p]);
}
}
}
}
}
}
@Override
public void run() {
// TODO Auto-generated method stub
}
};
class quad2 implements Runnable {
public quad2(int[] xy, int[] n2, int stop, int[] primeList2) {
//n ← 3x²+y²
//if (n ≤ limit) and (n mod 12 = 7):
// is_prime(n) ← ¬is_prime(n)
for (int p = 0; p < n2.length; p++){
for (int i = 0; i < xy.length; i ++){
for (int j = 0; j < xy.length; j ++){
/*if (n2[p] == 499){
if (n2[p] == (int) (3 * Math.pow(i, 2) + Math.pow(j, 2))){
System.out.println(i + ", " + j);
}
}*/
if(n2[p] == (int) (3 * Math.pow(i, 2) + Math.pow(j, 2))){
//System.out.println(n2[p]);
if (n2[p] <= stop + 1 && n2[p] % 12 == 7){
primeList2[p] = n2[p];
//System.out.println(n2[p]);
}
}
}
}
}
}
@Override
public void run() {
// TODO Auto-generated method stub
}
};
class quad3 implements Runnable {
public quad3(int[] xy, int[] n3, int stop, int[] primeList3) {
//n ← 3x²-y²
//if (x > y) and (n ≤ limit) and (n mod 12 = 11):
// is_prime(n) ← ¬is_prime(n)
for (int p = 0; p < n3.length; p++){
for (int i = 0; i < xy.length; i ++){
for (int j = 0; j < xy.length; j ++){
if(n3[p] == (int) (3 * Math.pow(i, 2) - Math.pow(j, 2))){
//System.out.println(n3[p]);
if (i > j && n3[p] <= stop + 1 && n3[p] % 12 == 11){
primeList3[p] = n3[p];
//ut.println(n3[p]);
}
}
}
}
}
}
@Override
public void run() {
// TODO Auto-generated method stub
}
};
Thread thr1 = new Thread(new quad1(xy, n1, stop, primeList1));
Thread thr2 = new Thread(new quad2(xy, n2, stop, primeList2));
Thread thr3 = new Thread(new quad3(xy, n3, stop, primeList3));
thr1.start();
thr2.start();
thr3.start();
thr1.join();
thr2.join();
thr3.join();
int j = 0;
for( int i = 0; i < primeList1.length; i++){
if (primeList1[i] != 0){
result[j] = primeList1[i];
j++;
}
}
for( int i =0; i < primeList2.length; i++){
if (primeList2[i] != 0){
result[j] = primeList2[i];
j++;
}
}
for( int i = 0; i < primeList3.length; i++){
if (primeList3[i] != 0){
result[j] = primeList3[i];
j++;
}
}
return result;
}
public static List<Integer> sieve(int[] results, int start, int stop) throws InterruptedException{
/*// eliminate composites by sieving
for n in [5, √limit]:
if is_prime(n):
// n is prime, omit multiples of its square; this is
// sufficient because composites which managed to get
// on the list cannot be square-free
for k in {n², 2n², 3n², ..., limit}:
is_prime(k) ← false*/
Arrays.sort(results);
List<Integer> primes = new ArrayList<Integer>();
List<Object> toRemove = new ArrayList<Object>();
List<Integer> cleanResults = new ArrayList<Integer>();
int c = 0;
int d = 0;
boolean test = false;
for(int i = 0; i < results.length; i++){
if (results[i] > 0){
test = false;
for (int j = 0; j < cleanResults.size(); j++){
if (results[i] == cleanResults.get(j)){
test = true;
break;
}
else {
test = false;
}
}
if (test == false){
cleanResults.add(results[i]);
//System.out.println(results[i]);
c++;
}
}
}
//System.out.println(cleanResults);
//This can cause false positives if the range does not include all primes from 1
primes = cleanResults;
for(Integer element : cleanResults){
for (int j = 1; j < stop + 1; j++){
c = (int) (j*Math.pow(element, 2));
if (j > 1){
d = (int) (j * element);
}
for(Object value: primes) {
if(value.equals(c)){
//System.out.println(c);
toRemove.add(c);
}
if (value.equals(d)){
toRemove.add(d);
}
}
}
}
primes.removeAll(toRemove);
return primes;
}
public static void test(List<Integer> primes, int start, int stop){
List<Integer> validPrimes = new ArrayList<Integer>();
List<Object> toRemoveMissed = new ArrayList<Object>();
List<Object> toRemoveFalsePos = new ArrayList<Object>();
int[] testCases = {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 , 101 , 103 , 107 , 109 , 113,
127 , 131, 137, 139, 149, 151, 157, 163, 167, 173,
179 , 181, 191, 193, 197, 199, 211, 223, 227, 229,
233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 ,
283 ,293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 ,
353, 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 ,
419 , 421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,
467 , 479, 487, 491, 499, 503, 509, 521, 523, 541 ,
547 , 557 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 ,
607 ,613 , 617 , 619 , 631 , 641 , 643 , 647 , 653 , 659 ,
661, 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 ,
739 , 743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809 ,
811 , 821, 823, 827, 829, 839, 853, 857, 859, 863 ,
877 , 881 , 883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 ,
947 ,953 , 967 , 971 , 977 , 983 , 991 , 997 , 1009 , 1013 ,
1019, 1021 ,1031 ,1033 ,1039 ,1049 ,1051 ,1061 ,1063 ,1069 ,
1087 , 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151 ,
1153 , 1163 , 1171 , 1181 , 1187 , 1193 , 1201 , 1213 , 1217 , 1223 ,
1229 ,1231 , 1237 , 1249 , 1259 , 1277 , 1279 , 1283 , 1289 , 1291 ,
1297, 1301 ,1303 ,1307 ,1319 ,1321 ,1327 ,1361 ,1367 ,1373 ,
1381 , 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451 ,
1453 , 1459 , 1471 , 1481 , 1483 , 1487 , 1489 , 1493 , 1499 , 1511 ,
1523 ,1531 , 1543 , 1549 , 1553 , 1559 , 1567 , 1571 , 1579 , 1583 ,
1597, 1601 ,1607 ,1609 ,1613 ,1619 ,1621 ,1627 ,1637 ,1657 ,
1663 , 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733 ,
1741 , 1747 , 1753 , 1759 , 1777 , 1783 , 1787 , 1789 , 1801 , 1811 ,
1823 ,1831 , 1847 , 1861 , 1867 , 1871 , 1873 , 1877 , 1879 , 1889 ,
1901, 1907 ,1913 ,1931 ,1933 ,1949 ,1951 ,1973 ,1979 ,1987 ,
1993 , 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053 ,
2063 , 2069 , 2081 , 2083 , 2087 , 2089 , 2099 , 2111 , 2113 , 2129 ,
2131 ,2137 , 2141 , 2143 , 2153 , 2161 , 2179 , 2203 , 2207 , 2213 ,
2221, 2237 ,2239 ,2243 ,2251 ,2267 ,2269 ,2273 ,2281 ,2287 ,
2293 , 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357 ,
2371 , 2377 , 2381 , 2383 , 2389 , 2393 , 2399 , 2411 , 2417 , 2423 ,
2437 ,2441 , 2447 , 2459 , 2467 , 2473 , 2477 , 2503 , 2521 , 2531 ,
2539, 2543 ,2549 ,2551 ,2557 ,2579 ,2591 ,2593 ,2609 ,2617 ,
2621 , 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687 ,
2689 , 2693 , 2699 , 2707 , 2711 , 2713 , 2719 , 2729 , 2731 , 2741 ,
2749 ,2753 , 2767 , 2777 , 2789 , 2791 , 2797 , 2801 , 2803 , 2819 ,
2833, 2837 ,2843 ,2851 ,2857 ,2861 ,2879 ,2887 ,2897 ,2903 ,
2909 , 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999 ,
3001 , 3011 , 3019 , 3023 , 3037 , 3041 , 3049 , 3061 , 3067 , 3079 ,
3083 ,3089 , 3109 , 3119 , 3121 , 3137 , 3163 , 3167 , 3169 , 3181 ,
3187, 3191 ,3203 ,3209 ,3217 ,3221 ,3229 ,3251 ,3253 ,3257 ,
3259 , 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331 ,
3343 , 3347 , 3359 , 3361 , 3371 , 3373 , 3389 , 3391 , 3407 , 3413 ,
3433 ,3449 , 3457 , 3461 , 3463 , 3467 , 3469 , 3491 , 3499 , 3511 ,
3517, 3527 ,3529 ,3533 ,3539 ,3541 ,3547 ,3557 ,3559 ,3571 ,
3581 , 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643 ,
3659 , 3671 , 3673 , 3677 , 3691 , 3697 , 3701 , 3709 , 3719 , 3727 ,
3733 ,3739 , 3761 , 3767 , 3769 , 3779 , 3793 , 3797 , 3803 , 3821 ,
3823, 3833 ,3847 ,3851 ,3853 ,3863 ,3877 ,3881 ,3889 ,3907 ,
3911 , 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989 ,
4001 , 4003 , 4007 , 4013 , 4019 , 4021 , 4027 , 4049 , 4051 , 4057 ,
4073 ,4079 , 4091 , 4093 , 4099 , 4111 , 4127 , 4129 , 4133 , 4139 ,
4153, 4157 ,4159 ,4177 ,4201 ,4211 ,4217 ,4219 ,4229 ,4231 ,
4241 , 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297 ,
4327 , 4337 , 4339 , 4349 , 4357 , 4363 , 4373 , 4391 , 4397 , 4409 ,
4421 ,4423 , 4441 , 4447 , 4451 , 4457 , 4463 , 4481 , 4483 , 4493 ,
4507, 4513 ,4517 ,4519 ,4523 ,4547 ,4549 ,4561 ,4567 ,4583 ,
4591 , 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657 ,
4663 , 4673 , 4679 , 4691 , 4703 , 4721 , 4723 , 4729 , 4733 , 4751 ,
4759 ,4783 , 4787 , 4789 , 4793 , 4799 , 4801 , 4813 , 4817 , 4831 ,
4861, 4871 ,4877 ,4889 ,4903 ,4909 ,4919 ,4931 ,4933 ,4937 ,
4943 , 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003 ,
5009 , 5011 , 5021 , 5023 , 5039 , 5051 , 5059 , 5077 , 5081 , 5087 ,
5099 ,5101 , 5107 , 5113 , 5119 , 5147 , 5153 , 5167 , 5171 , 5179 ,
5189, 5197 ,5209 ,5227 ,5231 ,5233 ,5237 ,5261 ,5273 ,5279 ,
5281 , 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387 ,
5393 , 5399 , 5407 , 5413 , 5417 , 5419 , 5431 , 5437 , 5441 , 5443 ,
5449 ,5471 , 5477 , 5479 , 5483 , 5501 , 5503 , 5507 , 5519 , 5521 ,
5527, 5531 ,5557 ,5563 ,5569 ,5573 ,5581 ,5591 ,5623 ,5639 ,
5641 , 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693 ,
5701 , 5711 , 5717 , 5737 , 5741 , 5743 , 5749 , 5779 , 5783 , 5791 ,
5801 ,5807 , 5813 , 5821 , 5827 , 5839 , 5843 , 5849 , 5851 , 5857 ,
5861, 5867 ,5869 ,5879 ,5881 ,5897 ,5903 ,5923 ,5927 ,5939 ,
5953 , 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053 ,
6067 , 6073 , 6079 , 6089 , 6091 , 6101 , 6113 , 6121 , 6131 , 6133 ,
6143 ,6151 , 6163 , 6173 , 6197 , 6199 , 6203 , 6211 , 6217 , 6221 ,
6229, 6247 ,6257 ,6263 ,6269 ,6271 ,6277 ,6287 ,6299 ,6301 ,
6311 , 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367 ,
6373 , 6379 , 6389 , 6397 , 6421 , 6427 , 6449 , 6451 , 6469 , 6473 ,
6481 ,6491 , 6521 , 6529 , 6547 , 6551 , 6553 , 6563 , 6569 , 6571 ,
6577, 6581 ,6599 ,6607 ,6619 ,6637 ,6653 ,6659 ,6661 ,6673 ,
6679 , 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761 ,
6763 , 6779 , 6781 , 6791 , 6793 , 6803 , 6823 , 6827 , 6829 , 6833 ,
6841 ,6857 , 6863 , 6869 , 6871 , 6883 , 6899 , 6907 , 6911 , 6917 ,
6947, 6949 ,6959 ,6961 ,6967 ,6971 ,6977 ,6983 ,6991 ,6997 ,
7001 , 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103 ,
7109 , 7121 , 7127 , 7129 , 7151 , 7159 , 7177 , 7187 , 7193 , 7207,
7211 ,7213 , 7219 , 7229 , 7237 , 7243 , 7247 , 7253 , 7283 , 7297 ,
7307, 7309 ,7321 ,7331 ,7333 ,7349 ,7351 ,7369 ,7393, 7411 ,
7417 , 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489 , 7499 ,
7507 , 7517 , 7523 , 7529 , 7537 , 7541 , 7547 , 7549 , 7559 , 7561 ,
7573 ,7577 , 7583 , 7589 , 7591 , 7603 , 7607 , 7621 , 7639 ,7643 ,
7649, 7669 ,7673 ,7681 ,7687 ,7691, 7699 ,7703 ,7717, 7723 ,
7727 , 7741, 7753, 7757, 7759, 7789 , 7793, 7817, 7823 , 7829 ,
7841 , 7853 , 7867 , 7873 , 7877 , 7879 , 7883 , 7901 , 7907 , 7919};
for (int i = 0; i < testCases.length; i++){
if (testCases[i] >= start && testCases[i] <= stop){
validPrimes.add(testCases[i]);
}
}
for(Integer element : primes){
for(Object value: validPrimes) {
if(value.equals(element)){
//System.out.println(c);
toRemoveMissed.add(element);
}
}
}
for(Integer element : validPrimes){
for(Object value: primes) {
if(value.equals(element)){
//System.out.println(c);
toRemoveFalsePos.add(element);
}
}
}
primes.removeAll(toRemoveFalsePos);
validPrimes.removeAll(toRemoveMissed);
System.out.println("There were " + primes.size() + " false positives.");
System.out.println(primes);
System.out.println("There were " + validPrimes.size() + " missed primes.");
System.out.println(validPrimes);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment