< script type="text/javascript">var mellipop_user_id = 473;

آموزش


+ الگوریتم عدد اول

در این پست قصد دارم که دو الگوریتم برای تعیین این که یک عدد اول هست یا نه بنویسم. البته لازم به ذکر هست که الگوریتم های نوشته شده قابل سریعتر شدن نیز می باشد که بعد از الگوریتم ها به توضیح آن می پردازم.

خوب شروع می کنیم:

برای یادگیری بیشتر بر روی ادامه ی مطلب کلیک بنمایید...


الگوریتم اول

این الگوریتم تعداد مقسوم علیه ها را چک می کند که اگر تعداد آنها برابر 2 بود عدد اول است.

٠) شروع

1) عدد N را از ورودی بگیر.

2) K <---------- 2

3) M <---------- 2

4) ادامه بده تا زمانی که M<N

          الف) باقیمانده R <--------- N/M

            ب) اگر R=0 آنگاه K=K+1

            ج) M <---------- M+1

5)  اگر K=2 آنگاه چاپ کن "عدد اول است" در غیر اینصورت چاپ کن "عدد اول نیست"

6) پایان

الگوریتم دوم

این الگوریتم مجموع مقسوم علیه ها را چک می کند که اگر مجموع مقسوم علیه ها با عدد برابر بود آنگاه عدد اول است.

٠) شروع

1) عدد N را از ورودی بگیر.

2) K <---------- N

3) M <---------- 2

4) ادامه بده تا زمانی که M<N

          الف) باقیمانده R <--------- N/M

            ب) اگر R=0 آنگاه K=K+1

            ج) M <---------- M+1

5)  اگر K=N آنگاه چاپ کن "عدد اول است" در غیر اینصورت چاپ کن "عدد اول نیست"

6) پایان

نکات لازم پیرامون الگوریتم ها:

نکاتی که لازم به ذکر است این است که بزرگترین مقسوم علیه یک عدد به غیر از خود عدد کوچکتر مساوی نصف آن عدد است. یعنی شما در قسمت بند 4 الگوریتم ها می توانید به این صورت قرار دهید:

4) ادامه بده تا زمانی که  M < N/2 

 و نکته ی دیگر این است که بنا بر لم اقلیدس اگر عددی اول نباشد حداقل یک مقسوم علیه دارد که از جذر آن کوچکتر مساوی است. پس اینجا نیز می توانیم بند  را به صورت زیر تغییر دهیم.

4) ادامه بده تا زمانی که M< sqr(N

 

نویسنده : محسن خلیقی ; ساعت ۱٢:۳۱ ‎ب.ظ ; ۱۳٩٠/۱/٩
تگ ها:
comment نظرات () لینک