### Project Euler's sieve, Winter 2015

The project's goal is about:

• Generating all prime numbers of type int.

• Using this set of prime numbers for decomposing arbitrary int values into prime factors e.g.:

1050 = 2 * 3 * 5 * 5 * 7

We start with the first task by implementing the Euler sieve algorithm. We may use a boolean array representing e.g. the first 100 primes:

boolean[] nonPrimes = new boolean[100];

This array will initially be filled with 100 false values. The idea is using the Euler sieve algorithm to turn all non-prime value to true (t) and leaving al prime index values at false (f):

Index | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| 13| 14 ...
------+--+--+--+--+--+--+--+--+--+--+---+---+---+---+--- ...
value | t| t| f| f| t| f| t| f| t| t|  t|  f|  t|  f|  t ...

Since we intend to deal with a large number Integer.MAX_VALUE of values (rather than just 100 ) we only consider odd values since even numbers are never prime except for the value 2. Thus 0 will represent 1, 1 will represent 3 and n will represent 2 * n + 1:

Index      | 0| 1| 2| 3| 4|  5|  6|  7| ...
-----------+--+--+--+--+--+---+---+---+ ...
represents | 1| 3| 5| 7| 9| 11| 13| 15| ...
-----------+--+--+--+--+--+---+---+---+ ...
value      | t| f| f| f| t|  f|  f|  t| ...

This requires a boolean array of just Integer.MAX_VALUE / 2. Start from the following skeleton:

public class Sieve {

final boolean[] nonPrimes;
final int numPrimesFound;

/**
* Creating a prime number Euler variant sieve
*
* @param limit The last value to be considered. May or may not be prime.
*
*/
public Sieve(final int limit) {
...// initialize nonPrimes and numPrimesFound.
}
...

/**
* Test if a given value is prime or not
*
* @param candidate The value in question.
*
* @return True if value is prime, false otherwise.
*/
public boolean isPrime(final int candidate) {
// Based on nonPrimes array
...
}
}

### Tip

Decompose the Euler sieve algorithm into smaller tasks and write appropriate tests. Start with small limit values (like 20) and extend to Integer.MAX_VALUE step by step.

Once you've finished implementing the sieve continue by implementing the second task of prime decomposition. We recall the initial example:

1050 = 2 * 3 * 5 * 5 * 7

So the primes 2, 3 and 7 appear with frequency 1 whereas 5 appears with frequency 2. For meaningful operations we introduce a new class combining a prime number and its corresponding frequency of appearance to represent prime factor decompositions appropriately:

/**
* Representing a single prime factor among with its
* frequency.
*
*/
public class PrimeFrequency {

/**
* The prime's immutable value.
*/
public final int prime;

/**
* The prime's frequency of appearance.
*/
int frequency;

/**
* @param prime {@link #prime}
* @param frequency The prime's frequency of appearance.
*/
public PrimeFrequency(final int prime, final int frequency) {
this.prime = prime;
this.frequency = frequency;
}

/**
* @return The prime factor's frequency of appearance.
*/
public int getFrequency() {
return frequency;
}

/**
* change the given frequency value.
* @param frequency change by this value.
*/
public void addFrequency(@SuppressWarnings("hiding") final int frequency) {
this.frequency += frequency;
}

@Override
public boolean equals(final Object obj) {
...
}
}

Now 2 * 3 * 5 * 5 * 7 may be represented by three (not four!) instances of PrimeFrequency. In order to represent the whole product implement a second container:

/**
* Representing integer values by an ordered set of prime factors among with
* their frequencies of appearance.
*
*/
public class PrimeFrequencySet {

private final static int initialCapacity = 16;

private PrimeFrequency[] store = new PrimeFrequency[initialCapacity]; // May grow due to new factors.

/**
* Searching for the existence of a {@link PrimeFrequency} with a matching
* prime value (frequency may be different!).
*
* Example: If the set contains the prime values {3, 7, 11} (we ignore
* frequencies) then searching for:
* <ul>
*   <li>3 return index 0</li>
*   <li>11 returns index 2</li>
*   <li>5 return -2</li>
*   <li>13 returns -3</li>
*   <li>2 returns -1</li>
* </ul>
*
* @param primeFrequency The candidate to be looked up.
*
* @return If a prime value match exists return its index. If no match
* exists return the negative value of the first index belonging to a set
* value having a larger prime value than the candidate (the "natural"
* insertion point) minus 1 (see example).
*/
public int find(final PrimeFrequency primeFrequency) {
...
}

/**
* Either add a new prime or just add a prime's frequency to an existing one.
*
* @param primeFrequency If the prime is already in the current set, add its
* frequency. Otherwise insert the new element preserving the order of prime
* values.
*/
public void add(final PrimeFrequency primeFrequency) {
...
}

/**
* @return The count of all prime factors.
*/
public int getLength() {
...
}

/**
* The prime factor corresponding to a given index.
* @param index .
* @return .
*/
public PrimeFrequency get(int index) {
...
}

/**
* @return All prime factors among with their respective frequencies.
*/
public PrimeFrequency[] get() {
...
}
}

This allows for decomposing arbitrary int values into their prime factors. We show a unit test example:

/**
* Prime factor decomposition.
*/
public class FactorTest {

final Sieve sieve = new Sieve(100000);

@Test
public void test2 () {
PrimeFrequencySet pfs = sieve.getPrimeFactors(12); ❶
Assert.assertEquals(2, pfs.getLength()); ❷
Assert.assertEquals(new PrimeFrequency(2, 2), pfs.get(0)); ❸
Assert.assertEquals(new PrimeFrequency(3, 1), pfs.get(1)); ❹
}
}
 Decomposing 12 into 2 * 2 * 3. We expect two factors: Prime factor 2 having frequency 2. Prime factor 3 having frequency 1. Check for first prime factor 2 of frequency 2. Check for second prime factor 3 of frequency 1.

For better illustration we provide the following example:

public class Driver {

/**
* @param args Unused
*/
public static void main( String[] args ) {

final Sieve sieve = new Sieve(Integer.MAX_VALUE);

int value = Integer.MAX_VALUE;
System.out.println("Value " + value + " is " +
(sieve.isPrime(value)? "" : "not") + " prime.");

value--; // Even Value

System.out.println("Value " + value + " is " +
(sieve.isPrime(value)? "" : "not") + " prime.");

value --; // Non-prime as well.
System.out.println("Value " + value + " is " +
(sieve.isPrime(value)? "" : "not") + " prime.");

value = Integer.MAX_VALUE - 1;
final PrimeFrequencySet pfs = sieve.getPrimeFactors(value);

System.out.print(value + " = ");
String separator = "";
for (PrimeFrequency pf : pfs.get()) {
for (int i = 0; i < pf.getFrequency(); i++) {
System.out.print(separator + pf.prime);
separator = " * ";
}
}
System.out.println();
}
}

This yields the following output:

Value 2147483647 is  prime.
Value 2147483646 is not prime.
Value 2147483645 is not prime.
2147483646 = 2 * 3 * 3 * 7 * 11 * 31 * 151 * 331

Depending on your implementation you may encounter the following heap memory related error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at de.hdm_stuttgart.mi.prim.sieve.Sieve.initSieve(Sieve.java:75)
at de.hdm_stuttgart.mi.prim.sieve.Sieve.<init>(Sieve.java:60)
at de.hdm_stuttgart.mi.prim.Driver.main(Driver.java:19)

The Java virtual machine by default may not provide enough heap space. You may enlarge the default allocation by setting the -Xmx. Eclipse provides a convenient way by means of a run time configuration (Menu Run --> Run Configurations):

Clicking the Arguments tab allows for setting the respective VM heap setting:

This allows for running your application with a maximum of 4 gigabytes of heap space.

With respect to automated unit testing (mvn test)you may want to set the same value in you pom.xml file

<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-surefire-plugin</artifactId>
<version>2.19</version>
<configuration>
<argLine>-Xmx4G</argLine>
</configuration>
</plugin>