Problems with Prime Numbers

[brriney]

I am beginning computer science major and I am completely lost with this. Can anyone help me figure these directions because they are very confusing at some parts. Any suggestions?

Write a program that calculates all prime numbers less than 10,000. The program works as follows:


1. Create a main method, and a method called ArrayList< Integer > sieve( int n ), which returns a list with all the prime numbers less than n. The main method calls sieve( 10,000 ), and prints out the results.

2. Inside of sieve(), do the following:
a. Call method createTrueArray( n ) to create a boolean array of size n.
b. Set cells 0 and 1 of the array to false. Each cell in the array represents a number, the boolean value represents whether it is prime or not. We start by assuming that all numbers greater or equal 2 are prime, and then we remove the ones that are not.
c. Loop over the array, starting at index 2.
d. First, remove all multiples of 2, by setting the values for 4, 6, 8, ... to false.
e. Then, look for the next number still marked true (in this case 3), and set all its multiples to false.
f. Repeat with all numbers that are marked true. When you are done, only prime numbers will be marked true.
g. Call method booleanArrayToIntList() to return a list of integers that contains the primes.

3. Method boolean[] createTrueArray( int n ) creates a boolean array of size n and initializes all its values to true.

4. Method ArrayList< Integer > booleanArrayToIntList( boolean[] booleans ) loops through booleans, and for each true value, it adds the corresponding number to a list. Finally, it returns the list.

[Twey]

This isn't confusing at all. It's an algorithm called the Sieve of Eratosthenes, and it goes something like this:

import java.util.ArrayList;

class Eratos {
  boolean[] createTrueArray(int n) {
    boolean[] r = new boolean[n];

    for(int i = n - 1; i >= 0; --i)
      r[i] = true;

    return r;
  }

  ArrayList<Integer> sieve(int n) {
    boolean[] r = createTrueArray(n);
    r[0] = r[1] = false;

    for(int i = 2; i > 0; i = nextTrue(r, i + 1))
      for(int j = i * 2; j < n; j += i)
        r[j] = false;

    return booleanArrayToIntList(r);
  }

  int nextTrue(boolean[] arr, int start) {
    for(int i = start; i < arr.length; ++i)
      if(arr[i])
        return i;

    return -1;
  }

  ArrayList<Integer> booleanArrayToIntList(boolean[] bools) {
    ArrayList<Integer> r = new ArrayList<Integer>();

    for(int i = bools.length - 1; i >= 0; --i)
      if(bools[i])
        r.add(i);

    return r;
  }

  public static void main(String[] args) {
    ArrayList<Integer> foo = (new Eratos()).sieve(10000);

    for(int i = foo.size() - 1; i >= 0; --i)
      System.out.print(foo.get(i) + " ");

    System.out.println();
  }
}

Disclaimer: we don't do homework usually; I'm only doing it because I feel like it and my Java's rusty; if you get kicked off the course for plagiarism or seeking help here it's not my fault; the solution you've been told to implement is not the best way of going about this.

[djr33]

Here's a creative method.

I'm gonna write it in PHP, 'cause I don't know Java, and I don't feel like answering a homework question anyway, plus this isn't how your instructor will want it. Anyway, here goes:

<?php

$lim=100; //set the upper limit
$i=1;
$comp=array(2);
$primes=array(2);
while($comp[0]<=$lim/2) {
   $p = 1;
   foreach($comp as $n) { $p = $p*$n; }
   if ($p<=$lim) {
      $nprimes[$i]=$p;
      echo implode(', ',$nprimes).'<br>';
      $i++;
      for($b=2;$comp[count($comp)-$b]!=$comp[count($comp)-1]&&count($comp)>$b;$b++) {}
      if (count($comp)==$b) {
          $b=1;
      }
      $comp[count($comp)]=$comp[count($comp)-$b];
   }
   else {
      for($x=2;$x<=10+($lim/2);$x++) {
         if (!in_array($x,$nprimes)) {
             $primes[$i]=$x;
            $comp[count($comp)-2]=$x;
            unset($comp[count($comp)-1]);
            break;
         }
      }
   }
echo $comp[count($comp)-1]."\n";
}
echo implode(', ',$primes);
?>

Edit: code is updated. it still doesn't work properly. it's a bit harder than I thought to do it backwards. Interesting, though. I may fix this up soon, but I'm not sure I will.

[Trinithis]

Or if the language supports generators, that would be fun to implement it using those.