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

CalmoSoft60
In reply to this post by Gil Egozi
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 ~)
Forever Squeak!