Prime numbers

For a coursework assignment i must implement the 'Sieve of Eratothenes' on a sorted array of number and then place all the prime numbers in an ArrayList. (I am using Java).

Here is the psuedo code algorithm.

Code:

---

Eratosthenes(n) {
  a[1] := 0                         
  for i := 2 to n do a[i] := 1
  p := 2
  while p2  <  n do {
    j := p2
    while (j  <  n) do {           
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1 
  }
  return(a)
}

---

And here is my Java code, but it doesn't work. I don't know what is wrong with it, it just hangs (possible infinate loop somewhere).

Code:

---

public void sievePrimes()
{ 
    numbers[0] = 0;
    int n = 100;
 
    for(int i=1; i<n; i++)
    {
        numbers[i] = 1;   
    }
    int p = 2;
    while(p*p <= n)
    {
        int j = p*p;   
        while(j <= n) //Error is possibly here, infinate loop!
        {
            numbers[j-1] = 0;
            j = j+p;
        }
        while(numbers[p] != 1)
        {
            p++; 
        }
    }
    for(int index=0; index < numbers.length; index++)
    {
        System.out.println(numbers[index]);   
    }
}

---

Any help would be great. Thanks.

Add p++ before while(numbers[p] != 1), otherwise you keep looping the same P (with your current code P is always 2).

Here is a VB Classic version for those who are interested:

VB Code:

Option Explicit
 
Private Function Eratosthenes(ByVal N As Long) As Long()
    Dim A() As Long, I As Long, P As Long, J As Long
    ' reserve enough space for the array
    ReDim A(N)
    ' initialize i
    I = 2
    ' loop from 2 to n and set all items to 1
    Do While I < N: A(I) = 1: I = I + 1: Loop
    ' initialize p and j
    P = 2
    J = 4
    ' loop while the starting number fits in the array
    Do While J < N
        ' loop while in the array
        Do While J < N
            ' nullify
            A(J) = 0
            ' keep jumping to every P item
            J = J + P
        Loop
        P = P + 1
        ' loop until we find a known prime
        Do Until A(P) = 1: P = P + 1: Loop
        ' prepare J for the next loop
        J = P * P
    Loop
    Eratosthenes = A
End Function
Private Sub Form_Load()
    Dim Test() As Long, lngA As Long
    Test = Eratosthenes(1000)
    For lngA = 1 To UBound(Test)
        If Test(lngA) = 1 Then Debug.Print lngA
    Next lngA
End Sub

If someone appreciates small memory usage more than speed, modify Long arrays to Byte :) Also... one would get more speed if the thing was done the other way: mark those items that aren't prime numbers so there would be no need to loop all items to 1 in the beginning of the function.

Quote:

---

Originally Posted by x-ice

Code:

---

public void sievePrimes()
{ 
    numbers[0] = 0;
    int n = 100;
 
    for(int i=1; i<=n; i++)
    {
        numbers[i] = 1;it must be i instead of 1   
    }
    int p = 2;
    while(p*p <= n)
    {
        int j = p*p;   
        while(j <= n) //Error is possibly here, infinate loop!
        {
            numbers[j-1] = 0;
            j = j+p;
        }
        while(numbers[p] != 1)
        {
            p++; 
        }
    }
    for(int index=0; index < numbers.length; index++)
    {
        System.out.println(numbers[index]);   
    }
}

---

Any help would be great. Thanks.

---

sorry but this code is quite confusing for me. i made a similar program long time back, but its in C++. see if it helps you:

Code:

---

/*Generating Prime Numbers using a procedure called
  sieve of Eratosthenes*/


#include<iostream.h>
#include<conio.h>

void main()
 {
  clrscr();
  int num[100],i,j;

  //FILL AN ARRAY OF 100 FROM 1 - 100

  for(i=0;i<100;i++)
        num[i] = i+1;

  //START FROM THE SECOND ELEMENT i.e. 2
  i = 1;
  while(i<=100)
  //for(i=2;i<=100;i++)
  {

  //PROCEED TO THE NEXT NON-ZERO ELEMENT

    if(num[i]!=0)
    {
      for(j=i+1;j<=100;j++)
      {

  //SET ALL OF THE MULTIPLES OF THE NON-ZERO ELEMENT TO 0

        if(num[j]%num[i]==0)
        {
          num[j] = 0;
        }
      }
    }
    i++;
  }

  //PRINTING THE NON-ZERO ELEMENTS OF THE ARRAY

  cout<<"\n\t\t\t  ==========================\n";
  cout<<"\t\t\t  Prime Numbers from 1 - 100";
  cout<<"\n\t\t\t  ==========================\n\n    ";
  for(i=0;i<100;i++)
  {
    if(num[i]!=0)
    {
      cout<<num[i]<<" ";
    }
  }
  getch();
 }

---

Thanks alot, got it working now.