(ENG/TR) Algorithm to find prime number (Prime number bulmak için algoritma)

ENGLISH

Question: Find if inputted number(n) is prime or not.

ANSWER

First of all, we should think that how we find prime numbers in real life. We take a number(ex. 11), and try to find its dividers except 1(if there is). 

In example of 11, first we look 2. "11%2" not equals 0. So continue with 3. "11%3" not equals 0... We continue like that until the end(which is 11%5). As you see, our last element which will be checked is half of given number. Because we can not find integer multiplier for integer greater than half of number. So if we check these conditions, we can find if this number is prime or not.

You can update this algorithm like that: check 2 in anywhere else, then start from 3, increase value by 2. It may increase performance a little bit; but we accept that for large numbers, these two algorithms have same complexity.

TÜRKÇE

Soru: Girilen sayının(n) asal olup olmadığını bulunuz.

CEVAP

İlk olarak, gerçek hayatta bir sayının asal olup olmadığını nasıl anladığımızı düşünmeliyiz. Bir sayı alıyoruz(örn. 11), ve o'nun 1 dışındaki bölenlerini bulmaya çalışıyoruz(eğer varsa).

11 örneğinde, ilk olarak 2'ye bakarız. "11%2", 0'a eşit değildir. Dolayısıyla 3 ile devam ederiz. "11%3", 0'a eşit değildir... Bu şekilde devam ederiz sona kadar(yani 11%5) devam ederiz. Gördüğünüz üzere, kontrol edilecek son eleman, sayımızın yarısıdır. Çünkü sayımızın yarısından büyük tam sayılar için, tam sayı olan bir çarpan bulamayız. Bundan dolayı bu durumları kontrol edersek, bu sayının asal sayı olup olmadığını bulabiliriz.

Bu algoritmayı şu şekilde güncelleyebilirsiniz: 2'yi başka bir yerde kontrol edin, Sonra 3'ten başlayıp, değeri 2 arttırın. Bu, performansı birazcık arttırabilir; ama biz her iki algoritma içinde, çok büyük sayılar için, bu algoritmaların aynı karmaşıklığa sahip olduğunu kabul ederiz.