Bir sayının asal çarpanlarını bulan program

i = 2
sayı = int(input("Sayıyı giriniz: "))
liste=[]
çarpan=[]

while i < sayı:

    if sayı % i == 0:
        print(i)
        liste.append(i)
    i += 1
del i
#print(liste)
for i in liste:
    bitir=True
    for a in liste:
        if (bitir):
            if(i==a):
                çarpan.append(i)
            elif(i%a==0):
                bitir=False
       
print("\n",*çarpan)


Yukarıdaki programı biraz daha geliştirip farklı bir işlev için kullandım. Ama bunu yapmak aklıma geldiğinde fıstık ezmesi yemiyordum :smile:.

1 Like
asal_mı = lambda x: [False for i in range(2,x-1) if x % i == 0] 
asallari_bul = lambda x: [i for i in range(2, x+1) if (x %i==0 and asal_mı(i)==[])]
a = [print(i) for i in asallari_bul(int(input("Sayıyı giriniz: ")))]

Canım sıkıldı fantazi yapayim dedim.

Kolay gelsin, eglendirici çalışma :slight_smile:

Bunu yapmak aklıma gelmediginde çarşıda 1 L lik meyve suyunu dikiyordum(tabi herkesin onunde degil,canı çeken olur,sakin bir yere geçtim) :smile:

2 Likes

Asal çarpanları değil ama sadece iki çarpanı bulan ve tarafımdan “ortak bölen algoritması” adı verilen bir kod yazdım. Program uzun değil ama, önce bu algoritmanın mantığını arzetmek isterim:

  1. Algoritmanın mantığı:
    Bilindiği üzere, asal olmayan bir sayının en küçük asal çarpanı karekökten küçüktür, bu nedenle sayımız kareköke kadar olan asallardan birine bölünürse çarpanlar bulunmuş olur. Eğer, a ve b asal olmak üzere n=a x b ise, en büyük bölen int(n**0.5) dir. Bölme algoritmasında kareköke kadar teksayılar veya asallar kullanmak elbette mantıklıdır, yani kullanacağımız bölenler sınırlıdır.
  2. Ortak bölen algo’sunda ise, adı üzerinde, basit bölme işlemi yapmıyoruz. Çift sayıları da olaya dahil ederek şansımızı arttırıyoruz. Nasıl? Çünkü n=a x b ise, a ve b çarpanlarının ayrı ayrı başka sayılarla çarpılması, n sayısıyla ortak böleni bulunan sayılar üretecektir. Sayılar sonsuzdur, o halde n ile ortak böleni bulunan sayılar da sonsuzdur. Bu algoritmada tek şart, aynı zamanda EBOB bulunmasında kullanılan Öklid algoritmasının da tek şartı olan, n ve diğer sayının “aralarında asal” olmasıdır. Sayımızla ortak böleni bulunan diğer sayıların miktarını sınırlamak zorundayız, çünkü sonsuz deneme yapamayız. Artık programa geçebiliriz.
    1nci usül:
   from math import gcd# python3.5 ve üstü. Yoksa from fractions import gcd
   def ortak3(sayı):
	    kr=int(sayı**0.5)+1;x1=1;fark=sayı-kr;deneme=0
	    n=(x for x in range(fark,sayı+1))#sayı jeneratörü-fark dan sayıya
	    while x1==1:
		    s=next(n);deneme+=1
		    if s==sayı:return deneme,"bu sayı asal"
		    x1=gcd(sayı,s)
	    return "deneme:"+str(deneme),x1,divmod(sayı,x1)[0]
    print(ortak3(sayı)

Bu usülde, asalı tespit etmek için sayı büyüdükçe çok fazla deneme yapmak gerekebilir ve fazla zaman harcanabilir. Bu nedenle asallık testini önce yapıp sonra algo’ya girmekte fayda umuyorum.
2nci usül:

    from math import gcd# python3.5 ve üstü. Yoksa from fractions import gcd
    import random
#Miller-Rabin asallık testi, ilginç bir algoritma, deterministik değil ama doğruluğu yüksek ve hızlı.
    def millertest(a,i,n):#Miller-Rabin asallık test algoritması
	if i==0:
		return 1
	x=millertest(a,i//2,n)#recursive fonksiyon
	if x==0:
		return 0
	y=(x*x)%n
	if (y==1) and (x!=1) and (x!=(n-1)):
		return 0
	if (i%2)!=0:
		y=(a*y)%n
	return y#kendisini kaç kere çağırdıysa o sayıda return den sonra çıkıyor


    def ortak3(sayı):
	    s=millertest(random.randint(2,sayı-2),sayı-1,sayı)
	    if s==1:return "bu sayı asal"
	    kr=int(sayı**0.5)+1;x1=1;fark=sayı-kr;deneme=0
	    n=(x for x in range(fark,sayı+1))#sayı jeneratörü-fark dan sayıya
	    while x1==1:
		    s=next(n);deneme+=1
		    if s==sayı:return #jenerator stop oluşmasın
		    x1=gcd(sayı,s)
	    return "deneme:"+str(deneme),x1,divmod(sayı,x1)[0]


[i for i in range(2, int(input('Bir sayi girin: '))-1) if not [a for a in range(2, i-1) if i%a==0]]