Ədədin sadə vuruqlara ayrılması

   Ədədin sadə vuruqlara ayrılması alqoritmi ədədin sadəliyinin yoxlanılması alqoritminə bənzəyir. Verilmiş n ədədinin ardıcıl şəkildə 2-dən başlayaraq natural ədədlərə bölünməsini yoxlayacağıq. Əgər natural ədəd olan i verilmiş n ədədini qalıqsız bölürsə, onda həmin natural ədədi sadə vuruqlar siyahısına əlavə edəcəyik. Bölünmənin nəticəsini isə n dəyişəninə mənimsədəcəyik. Bölünmə qalıqsız davam etdiyi müddətcə i bölənini sabit saxlayacağıq, qalıq alındıqda onu bir vahid artıracağıq.

   Alqoritmi √n olana qədər davam etdirmək lazımdır. Əgər sonda n ədədi 1-ə bərabər olmazsa, deməli o sadə ədəddir.  Çünki kvadrat kökündən böyük olmayan heç bir ədədə bölünmür. Odur ki, onu da sadə vuruqlar siyahısına əlavə etmək lazımdır.

n = int(input())

m = []
i = 2

while i * i <= n:     
    if n % i == 0:         
        m.append(i)         
        n = n // i     
    else:         
        i+=1 

if n > 1:
    m.append(n)

for i in m:
    print(i, end=" ")

Proqram icrasının nümunələri:

130
2 5 13

270
2 3 3 3 5

 

Ədədin sadəliyinin yoxlanılması

   Bildiyiniz kimi sadə ədədlər yalnız birə və özünə bölünən ədədlərdir. Məsələn 3 ədədi sadə ədəddir, çünki ancaq 1 və 3 ədədlərinə bölünür. 4 ədədi isə mürəkkəb ədəddir, çünki 1 və 4 ədədlərindən başqa həm də 2 ədədinə bölünür.

   Ədədin sadə olub-olmadığını tapmaq üçün bir neçə alqoritmdən istifadə olunur. Bu dərsimizdə biz bölünənlərin götürülməsi alqoritmini nəzərdən keçirəcəyik. Bölünənlərin götürülməsi alqoritmində verilmiş natural ədəd 2-dən başlayaraq öz kvadrat kökünə qədər (daxil olmaqla) bütün tam ədədlərə bölünür. Əgər bu bölənlərdən heç olmazsa biri verilmiş ədədi qalıqsız bölürsə, deməli baxılan ədəd mürəkkəb ədəddir. Yox əgər verilmiş ədəd göstərilən aralıqdakı ədədlərə qalıqlı bölünürsə, deməli baxılan ədəd sadə ədəddir.

from math import sqrt
 
n = int(input())
 
if n < 2:
    print("Ədəd 1-dən böyük olmalıdır!")
elif n == 2:
    print("Sadə ədəd")
else:
    limit = int(sqrt(n))
    i = 2
    m = True
    while i <= limit:
        if n % i == 0:
            print("Mürəkkəb ədəd")
            m = False
            break 
        i += 1 
    if m:
        print("Sadə ədəd")

Proqram icrasının nümunələri:

1
Ədəd 1-dən böyük olmalıdır!

17
Sadə ədəd

196
Mürəkkəb ədəd