Algoritme Untuk Menemukan Bilangan Prima yang Kurang Dari N


Ini adalah salah satu soal di situs projecteuler.net,

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Soal ini mungkin tidak terlalu sulit, tapi yang menantang di sini adalah bagaimana menemukan jawaban dengan algoritme yang paling bagus. Sehingga kita tidak terlalu lama menunggu jawaban keluar dari program. Dalam posting kali ini, saya akan memberikan beberapa algoritme untuk menyelesaikan soal di atas.

1. Brute Force

Ini adalah algoritme yang paling mudah di buat, dan mungkin algoritme yang pertama kali terpikir ketika membaca soal di atas. Algoritme ini terdiri dari dua loop, loop pertama untuk mendapatkan bilangan prima sebelum N dan loop ke dua untuk mengecek apakah nilai pada loop pertama itu bilangan prima atau bukan. Klo dikata2in mungkin agak susah nangkapnya, jadi mari kita lihat sourcecode nya saja.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Exercise1
{
    class Program
    {
        public static void Main()
        {
            double finish = 2000000;
            List l = new List();
            for (int i = 2; i < finish; i++){
                bool flag = true;
                for (int j = 2; i > j && flag; j++)
                    if (i % j == 0)
                        flag = false;
                if (flag) l.Add(i);
            }

            double sum = 0;
            foreach (var item in l)
            {
                sum += item;
                Console.Write("{0}, ", item);
            }
            Console.WriteLine("Jumlah: {0}", sum);
            Console.ReadKey();
        }
    }
}

2. Cek Ganjil

Seperti yang kita ketahui, bilangan prima itu pasti ganjil kecuali satu saja yang tidak ganjil yaitu bilangan 2. Nah, pada algoritme ini dilakukan eliminasi terhadap bilangan genap, yang sudah dipastikan bukan bilangan prima.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Exercise1
{
    class Program
    {
        public static void Main()
        {
            double finish = 10;
            List l = new List();
            l.Add(2);
            for (int i = 3; i < finish; i+=2){
                bool flag = true;
                for (int j = 3; i > j && flag; j+=2)
                    if (i % j == 0)
                        flag = false;
                if (flag) l.Add(i);
            }

            double sum = 0;
            foreach (var item in l)
            {
                sum += item;
                Console.Write("{0}, ", item);
            }
            Console.WriteLine("Jumlah: {0}", sum);
            Console.ReadKey();
        }
    }
}

3. Setengah Pembagi
Jika kita mengecek 7, maka yang dilakukan adalah: 7 % 2 != 0 | 7 % 3 != 0 | 7 % 4 != 0, nah setelah ini adalah pengulangan dari sebelumnya. Jika modulus bilangan sebelum setengahnya tidak ada yang sama dengan 0 maka, sesudah nya pun g ada.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Exercise1
{
    class Program
    {
        public static void Main()
        {
            double finish = 10;
            List l = new List();
            l.Add(2);
            for (int i = 3; i < finish; i+=2){
                bool flag = true;
                double half = i/2;
                for (int j = 3; i > j && flag && j < half; j+=2)
                    if (i % j == 0)
                        flag = false;
                if (flag) l.Add(i);
            }

            double sum = 0;
            foreach (var item in l)
            {
                sum += item;
                Console.Write("{0}, ", item);
            }
            Console.WriteLine("Jumlah: {0}", sum);
            Console.ReadKey();
        }
    }
}

4. Thread

Untuk thread ini, implementasinya blm tuntas saya coba, jadi blm saya sampaikan sourcecode nya di sini.

Jika ada para pembaca yang memiliki solusi yang lebih baik atau ingin mengomentari, saya persilahkan. Dengan ini diskusi saya nyatakan dibuka😀

About windupurnomo

I'm interested in programming. I am active with several programming such as Java, C #, C, JavaScript, HTML. I'm also develop desktop application (Java Swing), Mobile Application (Android), and Web programming (ASP MVC).
This entry was posted in programming and tagged , , , . Bookmark the permalink.

One Response to Algoritme Untuk Menemukan Bilangan Prima yang Kurang Dari N

  1. asfarian says:

    Bagaimana kalau bilangan prima yang sudah ditemukan disimpan dalam sebuah array?
    Ketika sebuah bilangan n hendak dicek keprimaannya, cukup dengan mencoba membaginya dengan semua angka dalam array yang kurang dari akar n. Kalau ada yang hasil pembagiannya != 0, berarti n bukan prima. Kalau n prima, masukkan n ke dalam array.

    Atau bisa pakai algoritme Sieve of Eratosthenes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s