September 20, 2021, 06:24:47

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

BlitzBot

• Jr. Member
• Posts: 1
[bb] Calculating Primes by Subirenihil [ 1+ years ago ]
« on: June 29, 2017, 00:28:43 »
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
18. Flip
20. If file<>0
23. EndIf
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
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

Nathaniel(Posted 1+ years ago)

That doesn't work but this does:
Code: [Select]
`;Created By: Subirenihil;Edited By: Bubble BoyGraphics 1024,768,16,1SetBuffer BackBuffer()Global primestofind=100000000If primestofind>2000000000 Then primestofind=2000000000p=2n=4Text 512,384,"Loading...",1,1Flipfile=WriteFile("Primes.dat")If file<>0 n=ReadInt(file) p=ReadInt(file)EndIf;txt\$=ReadLine(file);primestofind=primestofind+pDim primes(primestofind+p)If n=0 Or p=0 Or file=0 p=2 n=4 primes(0)=2 primes(1)=3Else For a=0 To p-1 primes(a)=ReadInt(file) NextEndIfCloseFile fileIf 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 fileEndIfClsIf p>=10 Then Text 0,0, "The tenth prime number is:              "+primes(9),0,0If p>=100 Then Text 0,20, "The hundredth prime number is:          "+primes(99),0,0If p>=1000 Then Text 0,40, "The thousandth prime number is:         "+primes(999),0,0If p>=10000 Then Text 0,60, "The ten-thousandth prime number is:     "+primes(9999),0,0If p>=100000 Then Text 0,80, "The hundred-thousandth prime number is: "+primes(99999),0,0If p>=1000000 Then Text 0,100, "The millionth prime number is:          "+primes(999999),0,0If p>=10000000 Then Text 0,120, "The ten-millionth prime number is:      "+primes(9999999),0,0If p>=100000000 Then Text 0,140, "The hundred-millionth prime number is:  "+primes(99999999),0,0If p>=1000000000 Then Text 0,160, "The billionth prime number is:          "+primes(999999999),0,0FlipWaitKeyEnd`-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 ModeOpen FileLoad PrimesClose FileCalculate PrimesOpen FileWrite PrimesClose FileEnd`The code I posted should work - it was copy/pasted directly from my working program. [/i]