Ən kiçik bölən (Həll təhlili)

$n$ ədədinin bütün mümkün bölənlərini $2$-dən başlayaq \sqrt{n}-ə qədər olan intervalda nəzərdən keçirək və ən kiçiyini tapaq. Əgər [2; \sqrt{n}] intervalında bölənlər tapılmasa, nəticə olaraq sadəcə $n$ ədədinin özünü alacağıq.

Misal

Əgər n = 21, onda ən kiçik bölən $3$ olacaq.

Əgər n = 13 (sadə ədəd), onda ən kiçik bölən $13$ olacaq.

Alqoritmin icrası

Giriş ədədini $n$ oxuyuruq.

scanf("%d", &n);

flag = 0 olaraq təyin edirik. $n$ ədədinin mümkün bölənlərini $2$-dən \sqrt{n}-ə qədər intervalda nəzərdən keçiririk. İlk (ən kiçik) bölən tapıldığında flag = 1 təyin edirik, tapılmış böləni çıxarırıq qə və döngünü sonlandırırıq.

flag = 0;
for (i = 2; i <= sqrt(n); i++)
  if (n % i == 0)
  {
    printf("%d\n", i);
    flag = 1;
    break;
  }

Əgər bölən tapılmasa, deməli, $n$ ədədi sadədir. Bu halda sadəcə $n$ ədədinin özünü çıxarırıq.

if (flag == 0) printf("%d\n", n);

Java icrası

import java.util.*;

class Main 
{
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    
    int flag = 0;
    for (int i = 2; i <= Math.sqrt(n); i++)
      if (n % i == 0)
      {
        System.out.println(i);
        flag = 1;
        break;
      }

    if (flag == 0) System.out.println(n);    
    con.close();
  }
}

Python icrası

import math

Giriş ədədini $n$ oxuyuruq.

n = int(input())

$n$ ədədinin mümkün bölənlərini $2$-dən \sqrt{n}-ə qədər intervalda nəzərdən keçiririk. İlk (ən kiçik) bölən tapıldığında onu çıxarır və döngünü sonlandırırıq.

for i in range(2, math.isqrt(n)+1):
  if n % i == 0:
    print(i)
    break

Əgər döngü təbii şəkildə (break istifadə edilmədən) sona çatırsa, else bloku icra olunacaq.

Əgər bölən tapılmasa, deməli $n$ ədədi sadədir. $n$ ədədinin özünü çıxarırıq.

else: # döngü bitərsə buraya keçəcəyik
  print(n)