Fwd: Sieve of Eratosthenes

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

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 + " ");
        }
    }
}

Hello Gil,

See the next code on Google

| potentialPrimes limit |
limit := 100.
potentialPrimes := Array new: limit.
potentialPrimes atAllPut: true.
2 to: limit sqrt do: [:testNumber |
    (potentialPrimes at: testNumber) ifTrue: [
        (testNumber * 2) to: limit by: testNumber do: [:nonPrime |
            potentialPrimes at: nonPrime put: false
        ]
    ]
].
2 to: limit do: [:testNumber |
    (potentialPrimes at: testNumber) ifTrue: [
        Transcript show: testNumber asString; cr
    ]
]

Greetings,
Gal Zsolt
(~ CalmoSoft ~)

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 << " ";
   }
}