fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		System.out.println(Arrays.toString(PituhGenerator.generate(10)));
  13. 		System.out.print(Arrays.toString(PituhGenerator.generate(50)));
  14. 	}
  15.  
  16. public static class PituhGenerator {
  17.     private static int[] primes;
  18.     private static ArrayList<Integer> multiplesOfPrimeFactors;
  19.  
  20.     static int[] generate(int n) {
  21.         primes = new int[n];
  22.         multiplesOfPrimeFactors = new ArrayList<Integer>();
  23.         primes[0] = 2;
  24.         multiplesOfPrimeFactors.add(2);
  25.         int primeIndex = 1;
  26.         for (int candidate = 3;
  27.              primeIndex < primes.length;
  28.              candidate += 2) {
  29.             if (isPrime(candidate))
  30.                 primes[primeIndex++] = candidate;
  31.         }
  32.         return primes;
  33.     }
  34.  
  35.     static boolean isPrime(int candidate) {
  36.         int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()];
  37.         int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor;
  38.         if (candidate == leastRelevantMultiple) {
  39.             multiplesOfPrimeFactors.add(candidate);
  40.             return false;
  41.         }
  42.         for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) {
  43.             int multiple = multiplesOfPrimeFactors.get(n);
  44.             while (multiple < candidate)
  45.                 multiple += 2 * primes[n];
  46.             multiplesOfPrimeFactors.set(n, multiple);
  47.             if (candidate == multiple)
  48.                 return false;
  49.         }
  50.         return true;
  51.     }
  52.  
  53. }	
  54. public static class PrimeGenerator {
  55.   private static int[] primes;
  56.   private static ArrayList<Integer> multiplesOfPrimeFactors;
  57.  
  58.   public static int[] generate(int n) {
  59.     primes = new int[n];
  60.     multiplesOfPrimeFactors = new ArrayList<Integer>();
  61.     set2AsFirstPrime();
  62.     checkOddNumbersForSubsequentPrimes();
  63.     return primes;
  64.   }
  65.  
  66.   private static void set2AsFirstPrime() {
  67.     primes[0] = 2;
  68.     multiplesOfPrimeFactors.add(2);
  69.   }
  70.  
  71.   private static void checkOddNumbersForSubsequentPrimes() {
  72.     int primeIndex = 1;
  73.     for (int candidate = 3;
  74.          primeIndex < primes.length;
  75.          candidate += 2) {
  76.       if (isPrime(candidate))
  77.         primes[primeIndex++] = candidate;
  78.     }
  79.   }
  80.  
  81.   private static boolean isPrime(int candidate) {
  82.     if (isLeastRelevantMultipleOfNextLargerPrimeFactor(candidate)) {
  83.       multiplesOfPrimeFactors.add(candidate);
  84.       return false;
  85.     }
  86.     return isNotMultipleOfAnyPreviousPrimeFactor(candidate);
  87.   }
  88.  
  89.   private static boolean
  90.   isLeastRelevantMultipleOfNextLargerPrimeFactor(int candidate) {
  91.     int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()];
  92.     int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor;
  93.     return candidate == leastRelevantMultiple;
  94.   }
  95.  
  96.   private static boolean
  97.   isNotMultipleOfAnyPreviousPrimeFactor(int candidate) {
  98.     for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) {
  99.       if (isMultipleOfNthPrimeFactor(candidate, n))
  100.         return false;
  101.     }
  102.     return true;
  103.   }
  104.  
  105.   private static boolean
  106.   isMultipleOfNthPrimeFactor(int candidate, int n) {
  107.    return
  108.      candidate == smallestOddNthMultipleNotLessThanCandidate(candidate, n);
  109.   }
  110.  
  111.   private static int
  112.   smallestOddNthMultipleNotLessThanCandidate(int candidate, int n) {
  113.     int multiple = multiplesOfPrimeFactors.get(n);
  114.     while (multiple < candidate)
  115.       multiple += 2 * primes[n];
  116.     multiplesOfPrimeFactors.set(n, multiple);
  117.     return multiple;
  118.   }
  119. }	
  120. }
Success #stdin #stdout 0.07s 32704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[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]
https://ideone.com/ODWN2t
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!