Ədəd sadədir? (Həll təhlili)

Bir ədədi sade adlanır, əgər o, yalnız özü və birini bölən olaraq qəbul edirsə.

Teorem. Əgər ədəd $n$ mürəkkəbdirsə, o zaman onun mütləq \sqrt{n}-dan böyük olmayan bir böləni vardır.

Sübut. Tutaq ki, $n$ — mürəkkəb ədəd və $d$ — onun bölənidir. Onda $n/d$ da $n$-in bölənidir. Fərz edək ki, $n$-in bütün bölənləri \sqrt{n}-dan böyükdür. O halda d > \sqrt{n} və n / d > \sqrt{n} bərabərsizlikləri eyni anda həyata keçir. Bu bərabərsizlikləri vuraraq:

yəni n > n. Bu ziddiyyətə gətirir. Beləliklə, əgər ədəd $n$ mürəkkəbdirsə, onun ən azı bir böləni \sqrt{n}-dan kiçik və ya bərabərdir.

Bir ədədin $n$ sadə olub-olmadığını yoxlamaq üçün onu $2$-dən \sqrt{n} daxil olmaqla bir çox ədədə bölünüb-bölünmədiyini yoxlamaq kifayətdir. Əgər $n$ bu ədədlərdən ən az birinə bölünürsə, o zaman $n$ mürəkkəbdir. Əks halda $n$ sadədir.

Alqoritmin tətbiqi

Giriş dəyəri $n$-i oxuyuruq.

scanf("%d",&n);

flag = 1 bayrağını qururuq. Bu o deməkdir ki, $n$ ehtimal edilən sadədir.

flag = 1;

$2$-dən \sqrt{n} daxil olmaqla $n$ ədədinin bütün mümkün bölənlərini təkrarlayırıq. Əgər $n$, $i$-yə bölünürsə, $n$ mürəkkəbdir, buna görə də flag = 0 təyin edirik.

for (i = 2; i <= sqrt(n); i++)
  if (n % i == 0)
  {
    flag = 0;
    break;
  }

$flag$ dəyərindən asılı olaraq cavabı çap edirik.

if (flag == 0) printf("No\n"); 
else printf("Yes\n");

Alqoritmin tətbiqi — funksiya

IsPrime funksiyası $n$ ədədinin sadə olub-olmadığını yoxlayır.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$-i oxuyuruq.

scanf("%d",&n);

$n$ ədədinin sadə olub-olmadığından asılı olaraq cavabı çap edirik.

if (IsPrime(n)) printf("Yes\n"); 
else printf("No\n");

Java tətbiqi

import java.util.*;

public class Main
{
  static boolean IsPrime(int n)
  {
    for(int i = 2; i <= Math.sqrt(n); i++)
      if (n % i == 0) return false;
    return true;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    if (IsPrime(n))
      System.out.println("Yes");
    else 
      System.out.println("No");
    con.close();
  }
}

Python tətbiqi

import math

IsPrime funksiyası $n$ ədədinin sadə olub-olmadığını yoxlayır.

def IsPrime(n):
  for i in range(2, int(math.sqrt(n))+1):
    if n % i == 0: return False
  return True

Proqramın əsas hissəsi. Giriş dəyəri $n$-i oxuyuruq.

n = int(input())

$n$ ədədinin sadə olub-olmadığından asılı olaraq cavabı çap edirik.

if IsPrime(n):
  print("Yes")
else:
  print("No")