Bilangan Prima dalam Fibonacci (Soal GemasTik)

Waktu itu sebenernya cuman iseng aja nyari soal-soal programming Gemastik tahun lalu. Pas dapet langsung kucoba aja ngerjain dari yang paling gampang. Tapi, Oh God! Soal programming yang termudah dalam Gemastik ternyata tidak semudah yang kubayangkan. Terang aja sih, ini kan soalnya udah tingkat nasional. Lagian skill programmingku juga masih termasuk newbie banget. ^^

Langsung aja neh soalnya:

Hitung berapa banyak bilangan prima yang ada di dalam deret Fibonacci dan berapa jumlah dari bilangan-bilangan prima tersebut?


INPUT
- Program menerima satu masukan, yaitu:
jumlah suku Fibonacci yang dikehendaki (n), dimana n merupakan bilangan bulat dengan rentang nilai 0 < N < 1000000000  
OUTPUT
- Program akan menghasilkan dua output, yaitu Integer pertama merepresentasikan banyaknya bilangan prima yang terdapat di deret Fibonacci tersebut. Integer kedua merepresentasikan jumlah dari bilangan-bilangan prima yang terdapat di deret Fibonacci tersebut. Integer pertama dan kedua dipisahkan oleh baris.
EXAMPLE
- Sebagai contoh, misal aku masukin 5, maka:
fibonacci: 1 1 2 3 5
prima: 2, 3, 5
output: program akan mengeluarkan output berupa banyak dan jumlah bilangan prima: 3 10

Yahh, bagi programmer pemula seperti aku soal di atas memang cukup memakan waktu. Berikut adalah pembahasan versi Ilham. Oh ya, kodenya kutulis dalam bahasa Java.

/**
* Prime On Fibonacci
* @author ilham
*/

import java.util.Scanner;

public class PrimeOnFibonacci {

public static boolean prime(int n){
int count=0;
for (int i = 1; i <= n; i++) {
if(n%i==0){
count++;
}
}
if(count==2){
return true;
}else{
return false;
}
}

public static void primeOnFibonacci(int n){
int a=1,b=1,c=0, angka=0, count=0, total=0;
for (int i = 1; i <= n; i++) {
if(i==1||i==2){
angka=1;
}else{
c=a+b;
a=b;
b=c;
angka=c;
}
if(prime(angka)){
total+=angka;
count++;
}
}
System.out.println(count+" "+total);
}


public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
primeOnFibonacci(n);
}
}

Melihat kasus ini, aku memakai dua algoritma. Algoritma fibonacci generator dan Algoritma prime checker. Tak usahlah kujelaskan kedua algoritma di atas, cz aku sudah pernah membahasnya dengan menggunakan bahasa C. Coba lihat di sini: fibonacci - prime. Dalam program ini aku membuat dua buah method, method prime dan primeOnFibonacci. Method prime ini hanya digunakan untuk mengecek bilangan prima saja dan method ini kumasukkan ke dalam method primeOnFibonacci. Jadi setiap angka fibonacci yang dihasilkan oleh program akan selalu dicek apakah termasuk bilangan prima atau bukan. Jika ya, maka variabel count akan bertambah untuk mendapatkan banyaknya bilangan prima dalam fibonacci. Sedangkan variable total akan menyimpan hasil penjumlahan bilangan-bilangan prima tersebut. That's simple, right? Sebenarnya source code di atas bisa lebih singkat lagi jika menggunakan algoritma rekursif. Tapi source code yang seperti ini akan lebih mudah dipahami untuk programmer pemula sepertiku. So, please enjoy yah bagi yang pemula. :)