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

فکر میکنم کلاس اول راهنمایی بودم که برای اولین بار در درس ریاضی با اعداد اول آشنا شدیم. قضیه خیلی ساده بود! هر عددی که فقط به خودش و یک تقسیم پذیر هست اسمش اول بود. اما اون موقه کسی به ما نگفت که چرا اصلا این اعداد اول مهم هستند . شاید اگه میگفتن هم نمیفهمیدیم !

برنامه زیر یک عدد از شما میگیره و همه اعداد اولی که از 1 تا اون عدده رو برای شما چاپ میکنه و در نهایت به میلی ثانیه نشون میده که اجرای برنامه چقدر طول کشیده. 

 

#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+1):

        ch=0

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

            if(i%j==0):

                ch=ch+1

        if(ch==2):

            print(i,end=' ')

isprime(n)

 

b = datetime.datetime.now()

c = b - a print( int(c.total_seconds() * 1000))

 

برنامه به این صورت عمل می‌کنه که یک عدد از شما میگیره و در ازای اون عدد تابع isprime رو فراخوونی میکنه. این تابع عددی که شما وارد کردید یعنی n رو میگیره. وقتی که n گرفته شده باید وارد یه حلقه for بشیم. چون باید تک تک عددهایی که کوچکتر از n  هستن چک بشن که ببینیم اول هستن یا نه و چون 1 عدد اول نیست حلقه رو با 2 شروع می‌کنیم. حالا برای همه این عددها باید عملیات چک انجام بشه. اگه هر کدوم از این عددها فقط بر خودشون و یک تقسیم پذیر بودن، عدد اول هستن. 

 

من این الگوریتم ناشیانه رو برای n=10000 امتحان کردم و 24 ثانیه طول کشید. الگوریتم بهتری وجود داره که زمان رو کم تر بکنه؟ نمیدونم!