Fwd: Sieve of Eratosthenes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Fwd: Sieve of Eratosthenes

Gil Egozi
Hi,
 I am resending this since i wan't a member, and the message is still somewhere in moderation-land.

 after looking at Ramon's version i noticed the java version isn't returning the primes, so we can remove the last select:
this cuts time in half down close to: 500

Integer>>sieveOfEratosthenes
    "generates primes up to self, educational algorithm, not for
production use"
    | primes |
    primes := ByteArray new: self.
    2 to: self do: [:each |
        (primes at: each) = 0 ifTrue: [each + each to: self
            by: each do: [:notPrime |
                        primes at: notPrime put: 1]]].

"-------------"
SmalltalkImage current snapshot: true andQuit: false
Smalltalk garbageCollect.
Smalltalk garbageCollect.
Smalltalk garbageCollect. "force full garbage collect"
Time millisecondsToRun: [1000000 sieveOfEratosthenes].

Gil

--
Many people would sooner die than think; In fact, they do so.
-- Bertrand Russell




Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Sieve of Eratosthenes

Rohith
This could be the Java implementation of the problem -
Ref - InterviewBit

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n)
    {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
        for (int p = 2; p * p <= n; p++){
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
                System.out.print(i + " ");
        }
    }
}
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Sieve of Eratosthenes

soorya25
In reply to this post by Gil Egozi
Hi, Below is the C++ implementation of the problem
Ref- Adaface

int checkPrime(int n) {
   if (n <= 1)
      return 0;

   for (int i = 2; i < n; i++)
      if (n % i == 0)
         return 0;

   return 1;
}

void Prime(int n) {
   for (int i = 2; i <= n; i++) {
      if (checkPrime(i))
         cout << i << " ";
   }
}