ALGORITMA BRUTE FORCE PENCARIAN BILANGAN PRIMA C++

Bilangan prima atau integer prima sering disingkat "prima" adalah sebuah integer positif p>1 yang tidak memiliki pembagi integer positif selain 1 dan p itu sendiri. Jadi,sebuah bilangan prima p adalah sebuah integer positif dengan tepat satu pembagi positif selain 1. Dengan demikian, bilangan prima adalah bilangan - bilangan yang tidak bisa difaktorkan.
Sebagai contoh, satu - satunya pembagi 13 adalah 1 dan 13, hal ini membuat 13 adalah sebuah bilangan prima. sementara itu angka 24 memiliki pembagi 1,2,3,4,6,8,12,24. hal ini membuat angka 24 bukanlah sebuah bilangan prima.

ALGORITMA BRUTE FORCE PENCARIAN BILANGAN PRIMA
Pertama - tama kita membuat suatu list yang akan di isi dengan bilangan prima yang kita dapatkan. Pada awalnya de dalam list tersebut tidak ada bilangan lain selain 3. Kemudian kita akan mengecek seluruh bilangan ganjil sampai dengan batas yang telah kita tentukan sendiri, dan membandingkannya dengan bilangan prima yang ada di dalam list. Jika bilangan tersebut adalah bilangan prima, kita bisa menambahkannya kedalam list bilangan prima tadi..
Maka pseudocode nya adalah sebagai berikut :

procedure deterministicPrimeSequence(end):
      if end < 2: return []
      if end < 3: return [2]
      primes = [3]
      for i in range(5,end,2):
            sqt = int(sqrt(i))
            for prime in primes:
                   if prime > sqrt:
                          primes.append(i)
                          break
                   if i%prime == 0 : break
            primes.insert(0,2)
            return primes

Nah,sekarang akan kita terapkan dalam sebuah program, pada kesempatan kali ini saya menggunakan C++. Berikut adalah source code cara untuk mencari bilangan Prima dari angka awal hingga angka akhir yang di inputkan dengan C++.
Sebagai contoh:
Jika user menginputkan:
     Angka awal = 1
     Dan angka akhir = 100

Maka program akan mencari seluruh bilangan prima yang ada pada range 1 – 100 dan menampilkannya di layar monitor.

Langsung saja saya jabarkan cara pembuatan programnya:

1. Untuk menentukan apakah n merupakan bilangan prima atau bukan, buatlah sebuah fungsi untuk membagi n dengan seluruh bilangan ganjil mulai dari 3 sampai akar dari n.
   mengapa hanya sampai akar n? karena seluruh bilangan yang berada di atas akar n yang merupakan faktor dari n, pasti memiliki pasangan faktor yang berada di bawah akar n. sehingga jika ada faktor di atas akar n, sudah pasti ditemukan faktor lainnya di bawah akar n. ini akan lebih menghemat perhitungan (maaf kalo bahasanya berantakan, saya gak terbiasa menjabarkan matematika.)
2. lakukan perulangan mulai dari angka awal sampai akhir dan chek setiap angka, apakah merupakan bilangan prima atau bukan dengan fungsi diatas
3. jika merupakan bilangan prima, tampilkan di monitor, jika bukan lanjutkan perulangan sampai akhir.

Source code

    #include <stdio.h>
    #include <conio.h>
    #include <math.h>
    #include <iostream>
   
    using namespace std;
    using namespace std;
    int isprima(int n)
    {
    int li;
    if (n == 2)
    return 1;
    if (n % 2 == 0 || n == 1)
    return 0;
    for(li = 3;li <= sqrt(n);li+=2)
    {
    if (n%li == 0)
    return 0;
    }
    return 1;
    }
    int main()
    {
    int li,banyak,awal,akhir;
    banyak = 0;
    cout<<"Masukkan angka awal : ";cin>>awal;
    cout<<"Masukkan angka akhir : ";cin>>akhir;
    cout<<endl<<"Bilangan Prima dari "<<awal<<" hingga "<<akhir<<" adalah:"<<endl;
    for(li = awal;li<=akhir;li+=2)
    if (isprima(li))
    {
       cout<<li<<" | ";
       banyak+=1;
       if (banyak % 5 == 0)
          cout<<endl;
    }
    cout<<endl<<endl<<"banyak bilangan prima = "<<banyak;
    getch();
    }