Redaksiya

Alqoritm Analizi

Ədəd əsas adlanır əgər onun yalnız bir və özündən başqa bölənləri yoxdursa.

Teorem. Əgər $n$ ədədi mürəkkəbsə, onda onun $n$ -dən böyük olmayan bir böləni mütləq var.

İsbat. Fərz edək ki, $n$ mürəkkəbdir və $d$ onun bölənidir. Onda $n / d$ də $n$ -in böləni olacaq. Əgər biz $n$ -in bütün bölənlərinin $n$ -dən böyük olduğunu fərz edək, onda $d > n$ və $n / d > n$ . Buradan $d * (n / d) > n * n$ və ya $n > n$ , bu isə ziddiyyətdir.

$n$ ədədinin əsas olub olmadığını yoxlamaq üçün, onun 2-dən $n$ daxil olmaqla hər hansı bir ədədə bölünüb bölünmədiyini yoxlamaq kifayətdir. Əgər $n$ onlardan ən azı birinə bölünürsə, onda $n$ mürəkkəbdir. Əks halda, o əsasdır.

Alqoritm İmplementasiyası

$n$ dəyərini oxuyun. Əvvəlcə flag = 1 olaraq təyin edin, bu o deməkdir ki, $n$ əsasdır.

scanf("%d", &n);
flag = 1;

$n$ ədədinin mümkün olan bütün bölənləri $i$ üzərində iterasiya edin. Əgər $n$ $i$ -yə bölünürsə, onda o mürəkkəbdir, flag = 0 olaraq təyin edin.

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

flag dəyərinə əsasən cavabı çap edin.

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

Alqoritm – Əsas Yoxlamaq Funksiyası vasitəsilə İmplementasiya

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

int n;

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

int main(void)
{
    scanf("%d", &n);
    if (IsPrime(n)) printf("Yes\n"); else printf("No\n");
    return 0;
}

Java İmplementasiyası

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 İmplementasiyası

import math

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

n = int(input())
if IsPrime(n):
    print("Yes")
else:
    print("No")