Python'da Mükemmel Sayı Programı: Bir sayının mükemmel olup olmadığı nasıl kontrol edilir?

Yayınlanan: 2021-01-29

Tanıtım

Doğru bölenlerinin toplamı (sayı dahil değil) sayıya eşitse, bir sayının mükemmel sayı olduğu söylenir.

Daha iyi bir fikir edinmek için bir örnek düşünelim, 6'nın uygun bölenleri 1, 2, 3'tür. Şimdi bu bölenlerin toplamı 6'ya (1+2+3=6) eşittir, yani 6'nın mükemmel bir sayı olduğu söylenir. . 12 gibi başka bir sayı düşünürsek, 12'nin tam bölenleri 1, 2, 3, 4, 6'dır. Şimdi bu bölenlerin toplamı 12'ye eşit değildir, dolayısıyla 12 mükemmel bir sayı değildir.

Python'da programlama, daha basit sözdizimi ve iyi okunabilirliği nedeniyle diğer dillere kıyasla nispeten daha basit ve daha eğlencelidir. Artık mükemmel sayı kavramını anladığımıza göre, bir sayının mükemmel sayı olup olmadığını kontrol etmek için bir python programı yazalım. Verilen kullanıcı girişinin mükemmel bir sayı olup olmadığını kontrol etmek için bir python kodu oluşturalım ve python ile kodlamanın eğlencesini keşfedelim. Uzmanlık kazanmak istiyorsanız, veri bilimi programlarımıza bir göz atın.

Okuyun: Python Model Programları

İçindekiler

Python Programı

Mükemmel bir sayı bulmak için temel bir çözüm, 2'den 1'e kadar döngü yapmak, uygun bölenlerinin toplamını korumak ve toplamın sayıya eşit olup olmadığını kontrol etmektir.

n=int(input(“sayıyı girin”))
toplam=1
i aralığında (2,n):
if(n%i==0):
toplam=toplam+i
if(toplam==n):
print(n”mükemmel bir sayıdır”)
Başka:
print(n”mükemmel bir sayı değil”)

Kodu inceleyelim.

İlk önce kullanıcı girdisiyle n'yi başlatıyoruz ve onu bir tamsayıya yazıyoruz çünkü varsayılan olarak kullanıcı girdisi python'da bir dize olarak okunur. n'nin mükemmel bir sayı olup olmadığını kontrol etmemiz gerekiyor. Toplamı 1 ile başlattığımızı unutmayın, çünkü 1 tüm tamsayılar (sıfır hariç) için uygun bir bölendir, böylece döngüdeki bir yinelemeyi hariç tutabilir ve doğrudan 2'den başlayabiliriz.

2'den 1'e döngü yapıyoruz ve uygun bir bölen ise toplama tamsayıları ekliyoruz. Ve son olarak, döngüden çıktığımızda elde edilen toplamın sayıya eşit olup olmadığını kontrol ediyoruz. Çok kolay değil mi?

Küçük Optimize Edilmiş Sürüm

Yukarıdaki program üzerinde kuru bir çalışma yaptıktan sonra, optimize edebilir miyiz diye bir sorumuz olabilir. Peki, ancak algoritmayı değiştirmeden yineleme sayısını sayı/2'ye indirebiliriz. Çünkü bir sayının/2 sayısından büyük bir tam böleni olamayacağı fikrine sahibiz.

n=int(input(“sayıyı girin”))
toplam=1
i aralığında (2,n//2+1):
if(n%i==0):
toplam=toplam+i
if(toplam==n):
print(n”mükemmel bir sayıdır”)
Başka:
print(n, “mükemmel bir sayı değil”)

Yukarıdaki snippet, bir öncekine neredeyse benzerdir, tek fark 2 numaralı döngüye kadardır. Float tipine dönüştürmekten kaçınmak için bir tamsayı bölümü yaptığımızı ve aralıktaki son tamsayı python döngüsünde dikkate alınmadığından n//2+1'e kadar döngü yaptığımızı unutmayın.

sınırlamalar

Belirli bir aralıkta mükemmel sayıları bulmamız istendiğinde, çözümümüz sayı^2 ile orantılı zaman tüketir, yani O(n²) zaman karmaşıklığı. Çünkü verilen aralıktaki her sayı üzerinde döngü yapmamız ve ardından her sayı için uygun bölenleri kontrol etmemiz gerekiyor. Ve birkaç sayı, mükemmel sayı koşulunu sağlar. Örneğin, 0 ile 1000 arasındaki mükemmel sayıların sayısı sadece 3'tür (6, 28, 496).

Bunun için uygun bölenleri bulmak için tüm öğeler üzerinde döngüye girmemize gerek olmayan optimize edilmiş bir çözüm var, Öklid'in formülü, 2 n −1(2 n − 1)'nin her ikisinin de n, (2 n − 1) olduğu durumlarda çift mükemmel bir sayı olduğunu belirtir. asal sayılar. Örneğin, 6, n'nin 2 olduğu yukarıdaki denklemi sağlar ve her ikisi de 2, 2 2 − 1 (2 2 − 1 = 3) asal sayılardır. Ancak, herhangi bir tek mükemmel sayı olup olmadığını bulmamız istendiyse, cevaplayamayız.

Ayrıca, her dilin saklayabileceği tamsayı aralığının bir sınırı olduğunu biliyoruz. Bu sınırlama ile en büyük mükemmel sayıyı bulmanın bir yolu olmayabilir.

Giriş sayımız büyükse tüm bu sınırlamalarla karşılaşılır, ancak giriş sayımız küçükse ilk çözümümüz daha kısa sürede çalışır.

Ayrıca Okuyun: Web Geliştirme için Python Çerçevesi

Çözüm

Tanımı biliyoruz ve mükemmel sayının arkasındaki kavramı anladık. Bir sayının mükemmel bir sayı olup olmadığını bulmak için temel bir çözümde yürüdük. İlk çözümü izledikten sonra, yineleme sayısını azaltarak onu biraz optimize ettik. Algoritmamızın sınırlarını aştık ve çift mükemmel sayıyı bulmak için Öklid'in formülünü tartıştık.

Artık bir sayının mükemmel sayı olup olmadığını kontrol etmek için python programından haberdarsınız. Kodu kendi başınıza yazmayı deneyin ve çakışan yinelemeler bulursanız en iyi duruma getirmeyi deneyin. Ayrıca, verilen sayı aralığında mükemmel sayıları bulmak için kod oluşturmayı deneyin.

Python, veri bilimi hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, pratik uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk sunan Veri Biliminde Yönetici PG Programına göz atın , sektör danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.

Python'da Mükemmel Sayı Programının karmaşıklıklarını açıklayın.

Bölenlerinin toplamına eşit olan sayılara mükemmel sayı denir. Bir sayının mükemmel olup olmadığını kontrol etmek için iki yaklaşımımız var. İlk yaklaşım, her “i” için “j” kez yinelediğimiz ve bölenlerini kontrol ettiğimiz için zaman karmaşıklığının O(n2) olduğu naif bir yaklaşımdır.
İkinci yaklaşım, zaman karmaşıklığının O(√n) olduğu optimize edilmiş çözümdür. Burada her sayıyı tekrar etmemize gerek yok. Öklid'in formülünü kullanarak doğrudan sonuca varabiliriz:
2n−1(2n − 1), burada n ve 2n asal sayılardır.
Ancak, bu formül tek mükemmel sayılar için çalışmaz ve bu nedenle onlar için başka bir yaklaşım bulmalıyız.

Perfect Number Programının yaklaşımlarının sınırlamaları nelerdir?

Bu yaklaşımların her ikisi de iyidir, ancak yalnızca bir dereceye kadar. Bazı teknik özellikler nedeniyle hiçbiri mükemmel bir yaklaşım olarak kabul edilemez. Bu yaklaşımların sınırlamaları aşağıdaki gibidir:

1. İlk ve saf yaklaşım daha kötüdür çünkü çok fazla zaman ve bellek tüketir ve O(n2) zaman karmaşıklığına sahiptir. Bunun nedeni, iç içe geçmiş bir döngü kullanmamız ve dış döngünün her öğesi için iç döngüyü n kez yinelememizdir. Bu yaklaşım naiftir ve daha büyük n değerleri için TLE verir ve bu nedenle önerilmez.
2. Ardından, sorunu O(√n)'de çözen optimize edilmiş bir yaklaşımımız var. Tek mükemmel sayılar devreye girmedikçe bu iyi bir yaklaşımdır. Sadece mükemmel sayılar için geçerli olan “Euclid'in çift mükemmel sayılar formülü”ne dayandığı için bu yaklaşımla tek mükemmel sayıları kontrol edemeyiz.

Python rekabetçi programlama için uygun mu?

Python, C/C++ ve hatta Java'dan evrimleşmiştir ve araştırma ve geliştirme amaçları için en uygun dil olarak kabul edilir. Ancak rekabetçi programlama söz konusu olduğunda, programlama topluluğunun çoğu Python'dan kaçınır. Python olmasının nedeni bu üç dil arasında en yavaş olanıdır.