Prime numbers

[x-ice]

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.

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).

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.

[Merri]

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:

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.

[Harsh Gupta]

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:

/*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();
 }

[x-ice]

Thanks alot, got it working now.