چاپ اعداد اول تا چند میلیون

چاپ اعداد اول تا چند میلیون
(برنامه به زبان بیسیک می باشد)
این برنامه تمام اعداد اول را تا عدد ورودی چاپ ‍‍‍می کند با این تفاوت که کمی پیشرفته تر است .
این برنامه درای سرعت بسیار زیادی می باشد و توانایی این را دارد که اعداد اول را در عرض چند ثانیه چاپ کند مثلا در عرض 13 ثانیه می تواند تعداد تمام اعداد اول تا یک میلیون را چاپ کند من برای 10 میلیون آزمایش کردم در عرض 200 ثانیه جواب گرفتم پس فرق بزرگ این برنامه در سرعت آن است .
با استفاده از خروجی این برنامه این نمودار کشیده شده است
این نمودار بر حسب افزایش عدد و در ستون بر حسب افزایش تعداد عدد اول تنظیم شده است
این نمودار به صورت بسیار دقیق اندازه گیری شده است و تعداد اعداد اول از یک تا 10 میلیون می باشد

با استفاده از این نمودار می توان به این نتیجه رسید که تعداد اعداد اول به صورت ثابت افزایش می یابد و این یک نتیجه ی تجربی است و نمی توان با استفاده از نمودار به یک استدلال قطعی رسید .
ما می توانیم با استفاده از این نمودار و بدست آوردن شیب آن معادله ای برای تعداد اعداد اول بنوسیم .
به طور مثال می توانیم تعداد اعداد اول تا 100 میلیارد را بدون کامپیوتر محاسبه کنیم که برای محاسبه با کامپیوتر کار بسیار مشکل و وقت گیر است

CLS
DIM a(10000)
INPUT k
g = INT(SQR(k))
ta = TIMER
PRINT "2",
FOR i = 3 TO g STEP 2
   c = 0
   FOR j = 2 TO i \ 2
      r = i MOD j
      IF r = 0 THEN c = c + 1: EXIT FOR
   NEXT j
   IF c = 0 THEN
      PRINT i,
      n = n + 1
      a(n) = i
   END IF
NEXT i
IF g MOD 2 = 0 THEN g = g + 1
FOR i = g TO k STEP 2
   c = 0
   FOR j = 1 TO n
      r = i MOD a(j)
      IF r = 0 THEN c = c + 1: EXIT FOR
   NEXT j
   IF c = 0 THEN
      PRINT i,
      m = m + 1
   END IF
NEXT i
PRINT : PRINT
PRINT "total avall number : "; m + n + 1
tb = TIMER
PRINT : PRINT
PRINT "timer = "; tb - ta
END

چهار چوب برنامه
این برنامه ابتدا اعداد اول را تا جذر عدد ورودی حساب می کند و در یک آرایه ذخیره می کند سپس اعداد باقیمانده ( اعداد بیشتر از جذر عدد ورودی )‌ را تقسیم بر آرایه ای که قبلا ذکر شد تقسیم می کند . اگر بر هیچ کدام تقسیم نشد آن را به عنوان عدد اول چاپ می کند .
بطور مثال ما عدد 100 را وارد می کنیم . ابتدا برنامه تعداد اعداد اول تا جذر 100 یعنی تا 10 را به صورت معمولی حساب می کند و در آرایه ذخیره می کند ما در آرایه این عدد ها را خواهیم داشت ( 3 ، 5 ، 7 )
سپس بقیه اعداد را فقط تقسیم بر این سه عدد می کند اگر بخشپذیر نبود آن را به عنوان عدد اول چاپ می کند .