Results 1 to 5 of 5

Thread: Finding prime numbers

  1. #1

    Thread Starter
    Fanatic Member x-ice's Avatar
    Join Date
    Mar 2004
    Location
    UK
    Posts
    671

    Resolved Finding prime numbers

    I have this code as an implementation of the 'Sieve of Eratosthenes'. But either it is super duper slow or it doesn't work. What is wrong with it?

    p.s. I am finding all the primes numbers in a sorted array with numbers 1-100 inclusive.
    Code:
    public void sievePrimes()
    {   
        numbers[0] = 0;
        int n = numbers[99];
       
        for(int i=1; i<n; i++)
        {
            numbers[i] = 1;    
        }
        int p = 2;
        while(p*p <= n)
        {
            int j = p*p;    
            while(j <=n)
            {
                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]);    
        }
    }
    Last edited by x-ice; Feb 25th, 2007 at 07:27 PM.

  2. #2
    Arabic Poster ComputerJy's Avatar
    Join Date
    Nov 2005
    Location
    Happily misplaced
    Posts
    2,513

    Re: Finding prime numbers

    while (j <= n) {
    numbers[j - 1] = 0;
    j = j + p;
    }
    Doesn't stop looping
    "I'm not normally a praying man, but if you're up there, save me... Superman!" - Homer Simpson
    My Blog

  3. #3

    Thread Starter
    Fanatic Member x-ice's Avatar
    Join Date
    Mar 2004
    Location
    UK
    Posts
    671

    Re: Finding prime numbers

    Quote Originally Posted by ComputerJy
    while (j <= n) {
    numbers[j - 1] = 0;
    j = j + p;
    }
    Doesn't stop looping
    How can i stop it from doing that and work correctly?
    Last edited by x-ice; Nov 22nd, 2005 at 04:40 AM.

  4. #4

    Thread Starter
    Fanatic Member x-ice's Avatar
    Join Date
    Mar 2004
    Location
    UK
    Posts
    671

    Re: Finding prime numbers

    This 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)
    }

  5. #5
    Arabic Poster ComputerJy's Avatar
    Join Date
    Nov 2005
    Location
    Happily misplaced
    Posts
    2,513

    Re: Finding prime numbers

    This is the algorithm as I know it:

    Code:
    public class Sieve {
      private static int upperLimit = 1000;
      private static boolean[] flags;
      public Sieve() {}
    
      public static void main(String[] args) {
        initialize(args);
        findPrimes();
        displayPrimes();
      }
    
      private static void initialize(String[] args) {
        if (args.length > 0) {
          upperLimit = Integer.parseInt(args[0]);
        }
        flags = new boolean[upperLimit + 1];
        for (int position = 0; position <= upperLimit; position++) {
          flags[position] = false;
        }
      }
    
      private static void findPrimes() {
        for (int position = 2; position <= Math.sqrt(upperLimit); position++) {
          if (!flags[position]) {
            int multiple = position * 2;
            while (multiple <= upperLimit) {
              flags[multiple] = true;
              multiple += position;
            }
          }
        }
      }
    
      private static void displayPrimes() {
        for (int position = 2; position <= upperLimit; position++) {
          if (!flags[position]) {
            System.out.print(position + ", ");
          }
        }
      }
    }
    "I'm not normally a praying man, but if you're up there, save me... Superman!" - Homer Simpson
    My Blog

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width