|
|
Post by bplus on Mar 19, 2024 15:57:17 GMT
Anyone with the slightest interest in numbers will be called by this little progie:
'simplest prime sieve.bas for QB64 (B+=MGA) 2017-09-15 fixed 2024-03-19 ' absolutely no optimization
' now looking to save lowest prime factors for the beginning of a First factors application
' sieving marks composites ONLY, primes are what is left when composites are crossed off
Const topN = 1000 ' need to know when to quit
Dim ff(topN) ' need array to hold numbers crossed off, ff stands for first factor
For pcandidate = 2 To topN ' absolutely no optimation here!!!!
If ff(pcandidate) = 0 Then ' this is next prime discovered so cross off all composites
For i = pcandidate * pcandidate To topN Step pcandidate 'staring at pcand ^ 2 all multiples of pcand
ff(i) = pcandidate ' one!???
' no should be pcandidate! yikes because then you can use ff to factor numbers!
Next
End If
Next
'results
Print "Here are primes to "; topN
For i = 2 To topN
If ff(i) = 0 Then c = c + 1: Print _Trim$(Str$(c)); "th -"; i;
Next
|
|
|
|
Post by bplus on Mar 19, 2024 16:02:08 GMT
If math is the language of the universe THEN number is the word of god! One is the source of all!
|
|
|
|
Post by bplus on Mar 19, 2024 22:03:21 GMT
converting to Long Type I see a need for an optimazation right away, we only have to try prime candidates to the SQR(topN)
Option _Explicit
'simplest prime sieve.bas for QB64 (B+=MGA) 2017-09-15 fixed 2024-03-19
' now looking to save lowest prime factors for the beginning of a First factors application
' Converting to Long type I made an optimization by stopping at Limit
' sieving marks composites ONLY, primes are what is left when composites are crossed off
Dim As Long topN, limit, pCandidate, i, c
topN = 1000000 ' top integer to go to, need to know when to quit
limit = Sqr(topN) ' this is how far prime candidates have to go to be a first factor in topN integers
Dim As Long ff(topN) ' array to hold numbers crossed off, ff stands for first factor
For pCandidate = 2 To limit ' limit is first optimization
For i = pCandidate * pCandidate To topN Step pCandidate 'starting at pcand ^ 2 all multiples of pcand
ff(i) = pCandidate ' no should be pcandidate! yikes because then you can use ff to factor numbers!
Next
Next
'results
Print "Here are primes to "; topN
For i = 2 To topN
If ff(i) = 0 Then c = c + 1: Print _Trim$(Str$(c)); "th -"; i;
Next
|
|
|
|
Post by bplus on Mar 20, 2024 0:10:59 GMT
now for something useful. (I see I still didn't get the sieve code right, it should have had
If ff(i) = 0 then ff(i) = pCandidate
sorry it's been awhile since i worked with this code. I found the error as soon as I tried factoring 999,999 which should have had 3 as first and 2nd factor for start it had 999, nope!
This should now factor any number up to topN which you can change but 1000000 gets calculated nice and quick!
Option _Explicit
'simplest prime sieve.bas for QB64 (B+=MGA) 2017-09-15 fixed 2024-03-19
' now looking to save lowest prime factors for the beginning of a First factors application
' Converting to Long type I made an optimization by stopping at Limit
' sieving marks composites ONLY, primes are what is left when composites are crossed off
Dim Shared As Long topN
Dim As Long limit, pCandidate, i, c, factorMe
topN = 1000000 ' top integer to go to, need to know when to quit
limit = Sqr(topN) + 1 ' this is how far prime candidates have to go to be a first factor in topN integers
Dim Shared As Long ff(topN) ' array to hold numbers crossed off, ff stands for first factor
For pCandidate = 2 To limit ' limit is first optimization
For i = pCandidate * pCandidate To topN Step pCandidate 'starting at pcand ^ 2 all multiples of pcand
' but we only want the earliest number that factors a number!!!
If ff(i) = 0 Then ff(i) = pCandidate ' no should be pcandidate! yikes because then you can use ff to factor numbers!
Next
Next
'results
Print "Here are primes to "; topN
For i = 2 To topN
If ff(i) = 0 Then c = c + 1: Print _Trim$(Str$(c)); "th -"; i;
Next
Print
'test some factoring of numbers
Do
Input "Enter a number to factor, 0 quits "; factorMe
If factorMe > 1 Then Print factors$(factorMe)
Loop Until factorMe < 2
Function factors$ (n As Long)
Dim f$
If n > topN Then factors$ = "Error: too high a number.": Exit Function
f$ = ""
While ff(n) > 1
f$ = f$ + Str$(ff(n)) + " "
n = n / ff(n)
Wend
factors$ = f$ + Str$(n)
End Function
|
|
Aaditya Parashar
Junior Member
Just somebody with an abnormal coding routine.
Posts: 95
|
Post by Aaditya Parashar on Mar 20, 2024 16:52:58 GMT
Exactly what I have been looking for a project, but thought it would not be worth my time after seeing this.
I am always looking for some code pieces with a lot of math or high level algorithms, and this is certainly one of them.
Thanks bplus.
|
|
|
|
Post by bplus on Mar 21, 2024 1:51:32 GMT
here is an interesting experiment in search of simple prime patterns of numbers
i added a couple of 0's to topN so i could run the test pattern a bit longer 3....1 form of numbers ie: 31, 331, 3331,...
Option _Explicit
_Title "prime sieve - a series of primes" ' b+ 2024-03-20
'simplest prime sieve.bas for QB64 (B+=MGA) 2017-09-15 fixed 2024-03-19
' now looking to save lowest prime factors for the beginning of a First factors application
' Converting to Long type I made an optimization by stopping at Limit
' sieving marks composites ONLY, primes are what is left when composites are crossed off
Dim Shared As Long topN
Dim As Long limit, pCandidate, i, c, factorMe
topN = 100000000 ' top integer to go to, need to know when to quit
limit = Sqr(topN) + 1 ' this is how far prime candidates have to go to be a first factor in topN integers
Dim Shared As Long ff(topN) ' array to hold numbers crossed off, ff stands for first factor
For pCandidate = 2 To limit ' limit is first optimization
For i = pCandidate * pCandidate To topN Step pCandidate 'starting at pcand ^ 2 all multiples of pcand
' but we only want the earliest number that factors a number!!!
If ff(i) = 0 Then ff(i) = pCandidate ' no should be pcandidate! yikes because then you can use ff to factor numbers!
Next
Next
' here is interesting series of prime numbers
Print "Number, factors:"
For i = 1 To 7
Print r&("3", i, "1"), factors$(r&("3", i, "1"))
Next
Function factors$ (n As Long)
Dim f$
If n > topN Then factors$ = "Error: too high a number.": Exit Function
f$ = ""
While ff(n) > 1
f$ = f$ + Str$(ff(n)) + " "
n = n / ff(n)
Wend
factors$ = f$ + Str$(n)
End Function
Function r& (digit$, repeat, endDigit$)
r& = Val(String$(repeat, digit$) + endDigit$)
End Function
they were ALL prime! (too bad the pattern does eventually end).
|
|
