December 04, 2020, 11:39:13 AM

Author Topic: [bb] Calculating Primes by Subirenihil [ 1+ years ago ]  (Read 640 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Calculating Primes by Subirenihil [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
Title : Calculating Primes
Author : Subirenihil
Posted : 1+ years ago

Description : <strike>There is no known way (that I know of) to calculate any faster (other than using a faster computer).</strike>

<strike>Please correct me if you find a faster method.</strike>

[EDIT]Well! 16 minutes after I post this I find this
<a href="codearcs5b52.html?code=1872" target="_blank">FAST Sieve of Eratosthenes[/url] by Andy_A
His goes WAY faster.
And I thought I was so smart.

His can calculate 10,000,000 primes in 10 seconds
I can calculate 10,000,000 primes in 30 minutes


Code :
Code: BlitzBasic
  1. ;If you want the primes for something, they are stored in the same folder as the program under "Primes.dat"
  2. ;The primes are stored as Ints with an 8-byte header
  3. ;The header consists of two Ints, the first is the last number tested, the second is the prime that is being searched for.
  4. ;Sorry for not commenting although it should be fairly simple.
  5. ;
  6. ;I can calculate the first 10,000,000 prime numbers within half an hour
  7. ;The data file can get somewhat large if you calculate large quantities of primes - 10,000,000 primes takes up about 40MB of harddrive
  8.  
  9. Graphics 1024,768,16,1
  10. SetBuffer BackBuffer()
  11. Global primestofind=100000000
  12. If primestofind>2000000000 Then primestofind=2000000000
  13.  
  14. p=2
  15.  
  16. n=4
  17. Text 512,384,"Loading...",1,1
  18. Flip
  19. file=ReadFile("Primes.dat")
  20. If file<>0
  21.         n=ReadInt(file)
  22.         p=ReadInt(file)
  23. EndIf
  24. ;txt$=ReadLine(file)
  25. ;primestofind=primestofind+p
  26. Dim primes(primestofind+p)
  27. If n=0 Or p=0 Or file=0
  28.         p=2
  29.         n=4
  30.         primes(0)=2
  31.         primes(1)=3
  32. Else
  33.         For a=0 To p-1
  34.                 primes(a)=ReadInt(file)
  35.         Next
  36. EndIf
  37. CloseFile file
  38.  
  39. If primestofind>p
  40.         x=False
  41.         pp=-1
  42.         t=0
  43.         Repeat
  44.                 If p Mod 1000=0 And pp<p
  45.                         Cls
  46.                         Text 512,384,"I have found "+p+" primes so far and checked through "+(n-1)+".",1,1
  47.                         If MilliSecs()-t>=30 Then Flip
  48.                         t=MilliSecs()
  49.                         pp=p
  50.                 EndIf
  51.                 sqrt=Floor(Sqr#(n))
  52.                 prime=True
  53.                 For a=0 To sqrt
  54.                         If primes(a)>sqrt
  55.                                 Exit
  56.                         ElseIf n Mod primes(a)=0
  57.                                 prime=False
  58.                                 Exit
  59.                         EndIf
  60.                         If KeyHit(1) Then x=True
  61.                         If x=True Then Exit
  62.                 Next
  63.                 If x=True
  64.                         prime=False
  65.                         n=n-1
  66.                         Exit
  67.                 EndIf
  68.                 If prime=True
  69.                         primes(p)=n
  70.                         p=p+1
  71.                 EndIf
  72.                 n=n+1
  73.                 If n=2147483647
  74.                         Cls
  75.                         Text 512,384,"The "+p+"th prime number ("+primes(p-1)+") is at the maximum for the int variable type.  Hit Enter to save and exit."
  76.                         Flip
  77.                         Repeat:Until KeyHit(28) Or KeyHit(156)
  78.                         Exit
  79.                 EndIf
  80.        
  81.         Until p=primestofind Or x=True
  82.        
  83.         Cls
  84.         Text 512,384,"Saving...",1,1
  85.         Flip
  86.         file=WriteFile("Primes.dat")
  87.         WriteInt file,n
  88.         WriteInt file,p
  89.         ;WriteInt file,primes(p-1)
  90.         For a=0 To p-1
  91.                 WriteInt file,primes(a)
  92.         Next
  93.         CloseFile file
  94. EndIf
  95.  
  96. Cls
  97. If p>=10 Then                   Text 0,0,       "The tenth prime number is:              "+primes(9),0,0
  98. If p>=100 Then                  Text 0,20,      "The hundredth prime number is:          "+primes(99),0,0
  99. If p>=1000 Then                 Text 0,40,      "The thousandth prime number is:         "+primes(999),0,0
  100. If p>=10000 Then                Text 0,60,      "The ten-thousandth prime number is:     "+primes(9999),0,0
  101. If p>=100000 Then               Text 0,80,      "The hundred-thousandth prime number is: "+primes(99999),0,0
  102. If p>=1000000 Then              Text 0,100,     "The millionth prime number is:          "+primes(999999),0,0
  103. If p>=10000000 Then             Text 0,120,     "The ten-millionth prime number is:      "+primes(9999999),0,0
  104. If p>=100000000 Then    Text 0,140,     "The hundred-millionth prime number is:  "+primes(99999999),0,0
  105. If p>=1000000000 Then   Text 0,160,     "The billionth prime number is:          "+primes(999999999),0,0
  106. Flip
  107. WaitKey
  108. End


Comments :


Nathaniel(Posted 1+ years ago)

 That doesn't work but this does:
Code: [Select]
;Created By: Subirenihil
;Edited By: Bubble Boy

Graphics 1024,768,16,1
SetBuffer BackBuffer()
Global primestofind=100000000
If primestofind>2000000000 Then primestofind=2000000000

p=2

n=4
Text 512,384,"Loading...",1,1
Flip
file=WriteFile("Primes.dat")
If file<>0
n=ReadInt(file)
p=ReadInt(file)
EndIf
;txt$=ReadLine(file)
;primestofind=primestofind+p
Dim primes(primestofind+p)
If n=0 Or p=0 Or file=0
p=2
n=4
primes(0)=2
primes(1)=3
Else
For a=0 To p-1
primes(a)=ReadInt(file)
Next
EndIf
CloseFile file

If primestofind>p
x=False
pp=-1
t=0
Repeat
If p Mod 1000=0 And pp<p
Cls
Text 512,384,"I have found "+p+" primes so far and checked through "+(n-1)+".",1,1
If MilliSecs()-t>=30 Then Flip
t=MilliSecs()
pp=p
EndIf
sqrt=Floor(Sqr#(n))
prime=True
For a=0 To sqrt
If primes(a)>sqrt
Exit
ElseIf n Mod primes(a)=0
prime=False
Exit
EndIf
If KeyHit(1) Then x=True
If x=True Then Exit
Next
If x=True
prime=False
n=n-1
Exit
EndIf
If prime=True
primes(p)=n
p=p+1
EndIf
n=n+1
If n=2147483647
Cls
Text 512,384,"The "+p+"th prime number ("+primes(p-1)+") is at the maximum for the int variable type.  Hit Enter to save and exit."
Flip
Repeat:Until KeyHit(28) Or KeyHit(156)
Exit
EndIf

Until p=primestofind Or x=True

Cls
Text 512,384,"Saving...",1,1
Flip
file=WriteFile("Primes.dat")
WriteInt file,n
WriteInt file,p
;WriteInt file,primes(p-1)
For a=0 To p-1
WriteInt file,primes(a)
Next
CloseFile file
EndIf

Cls
If p>=10 Then Text 0,0, "The tenth prime number is:              "+primes(9),0,0
If p>=100 Then Text 0,20, "The hundredth prime number is:          "+primes(99),0,0
If p>=1000 Then Text 0,40, "The thousandth prime number is:         "+primes(999),0,0
If p>=10000 Then Text 0,60, "The ten-thousandth prime number is:     "+primes(9999),0,0
If p>=100000 Then Text 0,80, "The hundred-thousandth prime number is: "+primes(99999),0,0
If p>=1000000 Then Text 0,100, "The millionth prime number is:          "+primes(999999),0,0
If p>=10000000 Then Text 0,120, "The ten-millionth prime number is:      "+primes(9999999),0,0
If p>=100000000 Then Text 0,140, "The hundred-millionth prime number is:  "+primes(99999999),0,0
If p>=1000000000 Then Text 0,160, "The billionth prime number is:          "+primes(999999999),0,0
Flip
WaitKey
End

-Bubble Boy


Subirenihil(Posted 1+ years ago)

 My code works on my system.WriteFile is actually opening the file for both read and write operations.  ReadFile is only opening it for read operations.  Since I'm only reading from the file it is unnecessary to use WriteFile, though there is no harm with using it.  But because I am only reading from the file, ReadFile is the command to use.  Otherwise I should use OpenFile.  WriteFile is unnecessary for loading the data.pseudocode:
Code: [Select]
Set Graphics Mode
Open File
Load Primes
Close File
Calculate Primes
Open File
Write Primes
Close File
End
The code I posted should work - it was copy/pasted directly from my working program. [/i]

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal