Project Euler – Problem 3

Bu problemde 600851475143 sayısının en büyük asal çarpanını bulmamız isteniyor.

Öyleyse bu devasa sayının en büyük asal çarpanını bulalım.

• İlk olarak bir sayının asal sayı olup olmadığını tespit eden bir “isPrime” fonksiyonunu oluşturalım. (Bu Fonksiyonu oluşturabildiğinizi varsyıyorum.)
• En büyük asal çarpanın tutulacağı, başlangıç değeri 0 olan “largePrimeNumber” değişkenini tanımlayalım.
• 2’den başlayıp 600851475143‘ün karakkökünden küçük olduğu sürece çalışacak bir döngü oluşturalım. (Burada karekök kullanmamızın nedeni, programın çalışma zamanını daha kısa tutmak.)
• Bu döngü içerisinde sayıların hem bir çarpan hem de asal olup olmama kontrolünü yapalım. Eğer koşullar sağlanırsa, sayıyı “largePrimeNumber” değişkenine atayalım.

Şimdi bu ifadeleri koda dökelim.

#include <stdio.h>
#include <math.h>


int isPrime(int number);

int main() {

    int number = 600851475143,
    largePrimeNumber = 0;

    for(int i=2; i <= sqrt(number); i++) {
        if(number % i == 0 && isPrime(i)) {
            largePrimeNumber = i;
        }
    }

    printf("%d", largePrimeNumber);  // 6857

    return 0;
}

int isPrime(int number) {

    for(int i=2; i<=sqrt(number); i++) {
        if(number % i == 0) {
            return 0; 
        }
    }

    return 1;
}

Ve sonuç 6857.