Pengujian Keprimaan Bilangan dengan Sieve of Erathostenes (Primality test with Sieve of Erathostenes)

today, i manage to write my blog post in English ;). but, first i must warn you, my English is bad, so if you don’t really understand with what i write, than  just read the code :P. For my first English post,  i choose to give better alternative for finding prime number than this post using sieve algorithm.

without further ado, here are the illustration how sieve algorithm work.

We start out with some set of numbers. Normally, that’s 1 to 100, but I don’t want to write all those, so I’m going to go from 1 to 30. The idea stays the same, though.

   1   2   3   4  5   6   7   8  9 10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30

We start by getting rid of 1, because the definition of ‘prime’ excludes 1:

  1   2   3   4  5   6   7   8  9  10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30

The smallest prime is 2.  But anything that is _divisible_ by 2 can’t be prime, right?  So we can keep 2, and cross out all its multiples:

    1   2   3   4  5   6   7   8  9  10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30

and remains

    2     3      5     7     9  
  11    13    15    17    19
  21    23    25    27    29

As you can see, that wipes out half the numbers we started with!  The next prime is 3.  We’re going to keep that, and again, we’ll wipe out the multiples of 3 – since if something is divisible by 3, it can’t be prime:

   2      3     5     7        
  11    13          17    19
         23     25          29

Now, what about 4? When we eliminated multiples of 2, we also eliminated multiples of 4, 6, 8, and every other even number! This is how the sieve works so quickly: every time you eliminate the multiples of a prime number, you never have to check those multiples. 

So we can just skip to the next prime number, which is 5. Removing the multiples of 5 leaves us with

    2     3     5     7        
  11    13          17    19 
          23                 29

And at this point, we’d need numbers over 30 in the sieve to see any effects, since everything we have left is prime.

But do you see the main idea? It’s sort of like a game that you can play with an audience full of people. Ask everyone to stand up. Then tell everyone with an ‘a’ in his or her last name to sit down. Then tell everyone with an ‘e’ in a last name to sit down. (Note that someone named ‘Apple’ would already be sitting.) Then do the same for ‘i’, ‘o’, and ‘u’. Who will be left standing? Only people with no vowels in their names! That is, people with names like Ng, or Kyzyl,
or Flynn, or Zbrtzk. 

If we order the vowels from most frequent to least frequent (eaoiu), then each vowel will eliminate fewer people – partly because it’s used less often, and partly because many people have more than one vowel in their names (in much the same way that 6 gets eliminated as a multiple of 2, so it isn’t around to be eliminated as a multiple of 3). 

Does this make sense?

next, we’ll write code in java (too) :). but hey, why don’t you  try this by yourself first, insya Allah I’ll post my code this afternoon 8) .

almost dzuhr here :)

as i promise before, here the code (in java)

public class Sieve {
    public static void main(String args[]) {
        // args[0] = max number to test
        int NUM = Integer.parseInt(args[0]);
        System.out.println(NUM);
        boolean [] flags = new boolean[NUM+1];
        int count = 0;
        for (int i=2; i <= NUM; i++) {             flags[i] = true;         }         System.out.println("Prime numbers unders " + NUM + " are: ");         for (int i=2; i <= NUM; i++) {             if (flags[i]) {                 // remove all multiples of prime: i                 for (int k=i+i; k <= NUM; k+=i) {                     flags[k] = false;                 }                 count++;                 System.out.print(i + ",");             }         }         System.out.print("Count: " + count + "\n");     } } [/sourcecode] sample output with args[0] = 30   [sourcecode language='html'] 30 Prime numbers unders 30 are:  2,3,5,7,11,13,17,19,23,29,Count: 10 [/sourcecode]

3 thoughts on “Pengujian Keprimaan Bilangan dengan Sieve of Erathostenes (Primality test with Sieve of Erathostenes)

  1. with that algorithm, the biggest number can be tested is 2^31-1 = 2147483647 (don’t ask how much time will be needed :P )
    so we need to change int data type with type long integer, to test bigger number.

    but my friend, believe me, there is no largest prime number, but if you wanna know recent largest prime number tested/found by scientist, this link will help u: largest known prime numbers

    here are top ten largest prime number

    rank prime digits who when reference
    1 243112609-1 12978189 G10 2008 Mersenne 46??
    2 237156667-1 11185272 G11 2008 Mersenne 45??
    3 232582657-1 9808358 G9 2006 Mersenne 44??
    4 230402457-1 9152052 G9 2005 Mersenne 43??
    5 225964951-1 7816230 G8 2005 Mersenne 42??
    6 224036583-1 7235733 G7 2004 Mersenne 41??
    7 220996011-1 6320430 G6 2003 Mersenne 40?
    8 213466917-1 4053946 G5 2001 Mersenne 39
    9 19249·213018586+1 3918990 SB10 2007
    10 27653·29167433+1 2759677 SB8 2005

    * koyone ngomong jowo luweh gampang ;)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s