ünite 5 · Klasik Algoritmalar · ders 5.1

Asal sayı testi

Bir sayının 1 ve kendisinden başka böleni var mı? Kareköküne kadar bakmak yeter.

7 dk 16 / 22

Asal: 1 ve kendisinden başka böleni olmayan, 1'den büyük sayı. Saf yöntem: 2'den n−1'e kadar hepsini dene, biri tam bölerse asal değil.

Daha akıllısı

n'nin böleni varsa, biri √n'den küçük ya da eşittir (bölenler çift çift gelir: 36 = 4×9 = 2×18). O yüzden √n'e kadar bakmak yeter: 10.000 için 100 deneme, 9.999 yerine.

Bayrak kalıbı

asal ← DOĞRU ile başla; bölen bulunca YANLIŞ yap ve dur. Döngü bittiğinde bayrak hâlâ DOĞRU ise asaldır.

Asal sayılar sadece matematik oyunu değil: internetteki şifreleme (HTTPS) çok büyük asallara dayanır.

akış şeması elips: başla/bitir · dikdörtgen: işlem · paralelkenar: girdi/çıktı · baklava: karar

flowchart TD
  A[/n oku/] --> B{n #lt; 2 ?}
  B -- Evet --> Y[/asal değil/]
  B -- Hayır --> C[i = 2, asal = DOĞRU]
  C --> D{i*i #lt;= n VE asal ?}
  D -- Evet --> E{n mod i = 0 ?}
  E -- Evet --> F[asal = YANLIŞ]
  E -- Hayır --> G[i = i + 1]
  F --> D
  G --> D
  D -- Hayır --> H[/asal yaz/]

sözde kod adımlar

1OKU n2asal ← (n ≥ 2)3i ← 24İKEN i × i ≤ n VE asal5  EĞER n MOD i = 0 İSE asal ← YANLIŞ6  i ← i + 17DÖNGÜ SONU8YAZ asal

aynısı C# ile C#

1int n = 29;2bool asal = n >= 2;3for (int i = 2; i * i <= n && asal; i++)4{5    if (n % i == 0) asal = false;6}7Console.WriteLine(n + (asal ? " asal" : " asal değil"));

adım adım izleme

Kutuların her adımdaki değeri. Kağıtta izleme tablosu tutarken tam bunu yaparsın.

#	satır	i	asal	not
1	n=29, i=2: 4 ≤ 29, 29 mod 2 = 1	2	DOĞRU	Bölmedi
2	i=3: 9 ≤ 29, 29 mod 3 = 2	3	DOĞRU	Bölmedi
3	i=4: 16 ≤ 29, 29 mod 4 = 1	4	DOĞRU	Bölmedi
4	i=5: 25 ≤ 29, 29 mod 5 = 4	5	DOĞRU	Bölmedi
5	i=6: 36 ≤ 29 ? Hayır	6	DOĞRU	Döngü bitti, bayrak DOĞRU → asal

senin sıran

1–100 arasındaki bütün asalları yazdır (asal testini döngü içinde çağır). Sonra "n'den küçük en büyük asal"ı bul.

Canlı Kod'da C# ile dene

kendini sına 1 asal mıdır? Algoritma bunu nerede yakalıyor?

Değildir; tanım "1'den büyük" der. asal ← (n ≥ 2) satırı 0 ve 1'i baştan eler.

İşaret bu tarayıcıda kalır. XP için giriş yap — her ders +15 XP.

önceki dersSıralama: kabarcık ve seçmeli sıradaki dersEBOB: Öklid algoritması