یک برنامه دیگر برای محاسبه اعداد اول با پایتون

وقتی بخوایم بدونیم که یه عدد اول هست یا نه کافیه که اون عدد رو بر تک تک اعداد کوچکتر و مساوی خودش تقسیم کنیم. اگه تعداد تقسیم‌هایی که باقی مووندشون صفر شده 2 تا باشه پس یعنی اون عدد اوله. مثل 13 که فقط بر 1 و 13 تقسیم پذیره. 

اما مثلا عددی مثل 18 اول نیست چون بر 1 ، 2 ، 3 ، 6 ، 9 و 18 تقسیم پذیره. در نظر داشته باشید که اگه ما تقسیم رو تا نصف عددمون هم انجام بدیم هم می‌تونیم بفهمیم که عددمون اول هست یا نیست. مثلا برای 13 تا نصفش ( که البته نصفش میشه 6.5  که رند میکنیم به 7) فقط 1 عدد تقسیم پذیر وجود دارد. 

و برای 18 تا نصفش ، 5 تا عدد تقسیم پذیر وجود داره. پس اینجا مرز تصمیم گیری ما میشه یک عدد تقسیم پذیر. شاید اینجوری از بار محاسباتی کم بشه. توی این برنامه سعی کردم چنین چیزی رو پیاده کم:

 

#this code show all prime numbers below n

import datetime

a = datetime.datetime.now()

n=int(input("plz enter a number: "))

def isprime(n):

         for i in range(2,n):

            ch=0

            for j in range(1,(i//2)+1):

                if(i%j==0):

                    ch=ch+1

            if(ch==1):

               print(i,end=' ')

isprime(n)

b = datetime.datetime.now()

c = b - a

print( int(c.total_seconds() * 1000))

همچنین اگه به جای حساب کردن تا نصف او عدد از جذر اون عدد هم استفاده کنید بهتر از اینم میشه : 

 

        for j in range(1,int((i**0.5)+1)):

 

چون جذر هر عدد دقیقا جاییه که میتونید عددهایی رو قبلش پیدا کنید که قابلیت تقسیم پذیری دارن.