Created
June 28, 2020 21:04
-
-
Save robertuniqid/1738f42740944088bba161c6de7af891 to your computer and use it in GitHub Desktop.
Fun : Example Refactor of PrimeGenerator
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Code from article here : https://qntm.org/clean | |
package literatePrimes; | |
import java.util.ArrayList; | |
public class PrimeGenerator { | |
private static int[] primes; | |
private static ArrayList<Integer> multiplesOfPrimeFactors; | |
protected static int[] generate(int n) { | |
primes = new int[n]; | |
multiplesOfPrimeFactors = new ArrayList<Integer>(); | |
set2AsFirstPrime(); | |
checkOddNumbersForSubsequentPrimes(); | |
return primes; | |
} | |
private static void set2AsFirstPrime() { | |
primes[0] = 2; | |
multiplesOfPrimeFactors.add(2); | |
} | |
private static void checkOddNumbersForSubsequentPrimes() { | |
int primeIndex = 1; | |
for (int candidate = 3; | |
primeIndex < primes.length; | |
candidate += 2) { | |
if (isPrime(candidate)) | |
primes[primeIndex++] = candidate; | |
} | |
} | |
private static boolean isPrime(int candidate) { | |
if (isLeastRelevantMultipleOfNextLargerPrimeFactor(candidate)) { | |
multiplesOfPrimeFactors.add(candidate); | |
return false; | |
} | |
return isNotMultipleOfAnyPreviousPrimeFactor(candidate); | |
} | |
private static boolean | |
isLeastRelevantMultipleOfNextLargerPrimeFactor(int candidate) { | |
int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()]; | |
int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor; | |
return candidate == leastRelevantMultiple; | |
} | |
private static boolean | |
isNotMultipleOfAnyPreviousPrimeFactor(int candidate) { | |
for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) { | |
if (isMultipleOfNthPrimeFactor(candidate, n)) | |
return false; | |
} | |
return true; | |
} | |
private static boolean | |
isMultipleOfNthPrimeFactor(int candidate, int n) { | |
return | |
candidate == smallestOddNthMultipleNotLessThanCandidate(candidate, n); | |
} | |
private static int | |
smallestOddNthMultipleNotLessThanCandidate(int candidate, int n) { | |
int multiple = multiplesOfPrimeFactors.get(n); | |
while (multiple < candidate) | |
multiple += 2 * primes[n]; | |
multiplesOfPrimeFactors.set(n, multiple); | |
return multiple; | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package literatePrimes; | |
import java.util.ArrayList; | |
public class PrimeGenerator { | |
private static int[] primes; | |
private static ArrayList<Integer> multiplesOfPrimeFactors; | |
protected static int[] generate(int n) { | |
primes = new int[n]; | |
multiplesOfPrimeFactors = new ArrayList<Integer>(); | |
// Set 2 as First Prime | |
primes[0] = 2; | |
multiplesOfPrimeFactors.add(2); | |
_attachSubsequentPrimes(); | |
return primes; | |
} | |
private static void _attachSubsequentPrimes() { | |
int primeIndex = 1; | |
for (int candidate = 3;primeIndex < primes.length;candidate += 2) { | |
if ( !isPrime( candidate ) ) | |
continue; | |
primes[primeIndex++] = candidate; | |
} | |
} | |
private static boolean isPrime(int candidate) { | |
if (isLeastRelevantMultipleOfNextLargerPrimeFactor(candidate)) { | |
multiplesOfPrimeFactors.add(candidate); | |
return false; | |
} | |
return ( isMultipleOfAttachedPrimeFactors(candidate) ? false : true ); | |
} | |
private static boolean isLeastRelevantMultipleOfNextLargerPrimeFactor(int candidate) { | |
int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()]; | |
int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor; | |
return candidate == leastRelevantMultiple; | |
} | |
private static boolean isMultipleOfAttachedPrimeFactors(int candidate) { | |
for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) { | |
if ( candidate != smallestOddNthMultipleNotLessThanCandidate(candidate, n) ) | |
continue; | |
return true; | |
} | |
return false; | |
} | |
private static int smallestOddNthMultipleNotLessThanCandidate(int candidate, int n) { | |
int multiple = multiplesOfPrimeFactors.get(n); | |
while (multiple < candidate) | |
multiple += 2 * primes[n]; | |
multiplesOfPrimeFactors.set(n, multiple); | |
return multiple; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Here's my take at a revision: https://github.com/marcospedreiro/prime-numbers/blob/master/src/main/java/org/example/prime_numbers/PrimeNumbers.java