## Squares

General FreeBASIC programming questions.
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ Albert.
You are correct, there are no patterns.
During the last 2500 years, thousands of mathematicians have looked for patterns.
Not one has yet found a reliable pattern.
IMO it is possible to prove mathematically that patterns are not possible.
The sieve of Eratosthenes is the only pattern.
dodicat
Posts: 6628
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

@ Albert
The gaps between the primes are the sticking points.
You can have two primes in the billions seperated by only 2.

@ Richard
The gears ~ Probably why British Leyland went wrong.

Maybe your assumption about gaps could be proven, maybe not. But if there is no pattern between the gaps the next best thing is random even gaps which doesn't seem to ring believable.

Another branch of Number theory must be created to solve the prime number problem and I daresay that is easier said than done.

Remember that Boolean algebra sat on the shelf for decades before a use was found for it.
I don't think the Prime cruncher is on the shelf yet.

But hey ~ nobody can accuse us here in humble squares of not doing our bit.

Anyway, here's the Highest common factor (Greatest common divisor) of two numbers bloatedly done using the prime factors of each number:

Code: Select all

` Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer    Dim As Integer i    #macro fill(x)    i=Ubound(p)+1    Redim Preserve p(1 To i)    p(i)=x    #endmacro    #macro Eliminate(x)    While number Mod x=0        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1    Wend    #endmacro    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull        Eliminate(2)    Eliminate(3)        While divisor<limit        divisor=divisor+6         Eliminate((divisor-1))        Eliminate((divisor+1))    Wend    If number>1 Then         fill(number)        check=check*number    End If    number=original    Return check=originalEnd FunctionSub PrintPrimeFactors(factors() As Ulongint)    Var msg=", ",acc=1ull    Print    For z As Integer=1 To Ubound(factors)        If z<Ubound(factors) Then msg=", " Else msg=""        acc=acc*factors(z)        Print factors(z) & msg;    Next z    Print     If Ubound(factors)=1 Then msg=" (Number is a PRIME)"    Print "Prime factors of " & acc & msg:Print "______":PrintEnd SubDim Shared As Integer startFunction IsIn(a() As Ulongint,num As Ulongint)As Integer    For x1 As Integer=start+1 To Ubound(a)        If num=a(x1) Then start=x1:Return -1    Next x1End FunctionFunction hcf(a1() As Ulongint,a2() As Ulongint) As Ulongint    Dim As Ulongint prod=1    For x1 As Integer=1 To Ubound(a1)        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)    Next x1    start=0    Return prodEnd Function' ============================================================Dim As Ulongint num1,num2,hnum1=934456222228000num2=388899002702800Redim As Ulongint factors1(),factors2(),Hcf_factors()If getprimefactors(num1,factors1()) Then printprimefactors(factors1())If getprimefactors(num2,factors2()) Then printprimefactors(factors2())h= hcf(factors1(),factors2())Print "For ";num1;" and ";num2Print "The Highest Common Factor = ";hPrintPrint "Prime factors of Highest common factor:"If getprimefactors(h,Hcf_factors()) Then printprimefactors(Hcf_factors())Print "done"Sleep `
albert
Posts: 5884
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

I tried some different numbers that I thought might be prime,
I don't know if they are or not, but your code returns a similar set of values for each.

Code: Select all

`Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer    Dim As Integer i    #macro fill(x)    i=Ubound(p)+1    Redim Preserve p(1 To i)    p(i)=x    #endmacro    #macro Eliminate(x)    While number Mod x=0        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1    Wend    #endmacro    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull        Eliminate(2)    Eliminate(3)        While divisor<limit        divisor=divisor+6         Eliminate((divisor-1))        Eliminate((divisor+1))    Wend    If number>1 Then         fill(number)        check=check*number    End If    number=original    Return check=originalEnd FunctionSub PrintPrimeFactors(factors() As Ulongint)    Var msg=", ",acc=1ull    Print    For z As Integer=1 To Ubound(factors)        If z<Ubound(factors) Then msg=", " Else msg=""        acc=acc*factors(z)        Print factors(z) & msg;    Next z    Print     If Ubound(factors)=1 Then msg=" (Number is a PRIME)"    Print "Prime factors of " & acc & msg:Print "______":PrintEnd SubDim Shared As Integer startFunction IsIn(a() As Ulongint,num As Ulongint)As Integer    For x1 As Integer=start+1 To Ubound(a)        If num=a(x1) Then start=x1:Return -1    Next x1End FunctionFunction hcf(a1() As Ulongint,a2() As Ulongint) As Ulongint    Dim As Ulongint prod=1    For x1 As Integer=1 To Ubound(a1)        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)    Next x1    start=0    Return prodEnd Function' ============================================================Dim As Ulongint num1,num2,h'num1=934456222228000'num2=388899002702800num1=10000000000000001num2=30000000000000003Redim As Ulongint factors1(),factors2(),Hcf_factors()If getprimefactors(num1,factors1()) Then printprimefactors(factors1())If getprimefactors(num2,factors2()) Then printprimefactors(factors2())h= hcf(factors1(),factors2())Print "For ";num1;" and ";num2Print "The Highest Common Factor = ";hPrintPrint "Prime factors of Highest common factor:"If getprimefactors(h,Hcf_factors()) Then printprimefactors(Hcf_factors())Print "done"Sleep `
Destructosoft
Posts: 88
Joined: Apr 03, 2011 3:44
Location: Inside the bomb
Contact:

### Re: Squares

Richard wrote: it is possible to prove mathematically that patterns are not possible.
The sieve of Eratosthenes is the only pattern.
Obviously that's a contradiction. Either the sieve is a pattern and therefore patterns are possible, or patterns are NOT possible and therefore the sieve is not a pattern.
dodicat
Posts: 6628
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

Hi Albert.
Looks ok.
Remember that the (highest common factor) prime factors are those factors which are common to the prime factors of each number.
It is an intersection of the prime factors for each number
2 2 5 7 11 23 101
and
2 2 2 3 7 17 23 103
the intersection is
2 2 7 23

If you check all the prime factors shown for numbers you should be able to distinguish them.

I've been thinking again about the sequences of numbers for these primes, the only way to get them seems is to evolve them (in the year 2012 anyway).
A bit like the Fibonacci sequence ~ loosly
But SEEMS is the keyword here.
Anyway, I've obtained the Highest common factor the other way here.
That is find ALL the factors for each number and get the (Highest COMMON factor to each group)
It's still bloatware, but I'm getting a bit fed up with prime numbers now.
In this one you enter your numbers at runtime, more than two if you wish.

Code: Select all

`Sub AllFactors(N As Ulongint,factors() As Ulongint)  'partially optimized     #macro bsort(array)    For p1 As Integer  = 1 To Ubound(array) - 1        For p2 As Integer  = p1 + 1 To Ubound(array)              If array(p1)>array(p2) Then Swap array(p1),array(p2)        Next p2    Next p1    #endmacro       Dim As Ulongint c    For i As Ulongint = 1 To Sqr(N)               If N Mod i=0 Then            C += 1             Redim Preserve factors(c)            factors(c)=i            If N <> i^2 Then                 C += 1                 Redim Preserve factors(c)                factors(c)=n\i            End If         End If     Next i    bsort(factors)End SubFunction hcf(num1 As Ulongint,num2 As Ulongint) As Ulongint    Redim As Ulongint A1(),A2()    AllFactors(num1,A1())    AllFactors(num2,A2())    Dim As Ulongint max=1    For x1 As Integer=1 To Ubound(a1)        For x2 As Integer=1 To Ubound(a2)            If a1(x1)=a2(x2) Then                max=a1(x1)            End If        Next x2    Next x1    Return maxEnd Function' =============================================================Dim As Ulongint number,x,lcmPrint "More than two numbers if you wish, enter 0 to end the inputs"PrintInput "FIRST NUMBER ";numberlcm=numberDo    Input " Next number ";x    If x>0 Then        number=hcf(number,x)        lcm=lcm*x\hcf(lcm,x)    End IfLoop Until x=0PrintPrint "HCF = ";numberPrint "LCM = ";lcmSleep `
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ Destructosoft.

Define Pattern.

Albert is looking for patterns in the digits when primes are written in base 10. Since primes are more fundamental than the base 10 number system, I cannot see how that could possibly work without writing the number n in every prime base below Sqrt(n) and looking for one representation that ends in zero. That is more effort than factorising.

Generating primes with a sieve is the only “patterned” way of finding primes. Given an arbitrary number you must advance the sieve to that number, which is again, factorising.

The tool called a sieve has a pattern. Prime numbers do not.
albert
Posts: 5884
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
It may be that; there are no patterns in Prime numbers.
But some patterns are so complex , like tree bark , dog , cat or cow or butterfly color patterns.

I imagine there is either a single whole pattern, or possibly many different interacting patterns.

Thats why i had thought to sort the primes into their ending digits and check values and gaps,
but I found no immediatley apparent pattern.

It may be that there is some type of Space-Time wormhole patterns that go into a wormhole at one number and come out further down the numberline.
albert
Posts: 5884
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
@Dodicat
I found some patterns!!!! in lucky 7's
First; you have to dick with the "filename" var to point to your file with primes 1 to ??

First it stops at 14 and then every 7.
Just space through and watch the greens and blues making the patterns. (some don't have a 7 or 14 pattern.)
The first pattern centers at 7 and goes center -7 to center +7 (The patterns aren't sequential they are MIRRORED.)

Code: Select all

`'===============================================================================        '===============================================================================        #include "file.bi"'===============================================================================        '===============================================================================        'Get Primes from file'===============================================================================        '===============================================================================        dim as ulongint low  =          1dim as ulongint high = 100000'===============================================================================dim as string filename = "C:\USB\MY-FB-PROGRAMS-023\Prime-Numbers\PRIMES\" + str(low) + "_" + str(high) + ".txt"if not FileExists(filename) then    color 14        print "File Name Doesnt' Exist."        print        print "Press a key to END."    color 7    sleep    endend ifredim as string Primes(0 to high)dim as string inputsdim as ulongint countopen filename for input as #1    do        input #1,inputs        count = val(inputs)        Primes(count) = inputs        loop until eof(1)close #1Print "Got Primes form file, Press a key to start.."sleep'==============================================================================='===============================================================================redim as string others(0 to high)for a as ulongint = 0 to high    others(a) = str(a)    if Primes(a) <> "" then others(a)=""nextdim as ulongint n,n1dim as double Remainderdim as string num1 , a1dim as ulongint mods=14for a as ulongint = 0 to ubound(Primes)    num1=others(a)    if num1="" then num1 = Primes(a)    'if right(num1,1)<>"0" then    'if right(num1,1)<>"2" then    'if right(num1,1)<>"4" then    'if right(num1,1)<>"5" then    'if right(num1,1)<>"6" then    'if right(num1,1)<>"8" then    Remainder = 0    for n1 = 1 to len(num1) step 1        for n = 1 to n1 step 1            a1 = str( abs( cint(num1[n1-1]-48) - cint(num1[n-1]-48) ) )            a1 = a1 + string(len(num1)+len(num1)-n-n1,"0")            Remainder = (Remainder + (valulng(a1) ))        next    next    if others(a) = "" then color 9 : print "Prime = " ; num1 , "Remainder = " ; remainder , "Diff = " ; (remainder ) + val(num1)  : color 7    if others(a)<> "" then color 10: print "Other = " ; num1 , "Remainder = " ; remainder , "Diff = " ; (remainder ) + val(num1) : color 7    'sleep 1000    'end if    'end if    'end if    'end if    'end if    'end if    if val(num1)<>0 and val(num1) mod mods = 0 then sleep : cls : mods+=7next'===============================================================================    '===============================================================================    'End Program'===============================================================================    '===============================================================================    sleepEND`

@Dodicat
How do we make a program for detecting the mirrored pattterns.
It might be that they are mirrored with infinity, where infinity is not prime while infinity -1 is prime.
But my prediction is that there are certain numbers where the mirroring begins and ends,
where you have centers mod 7 = 0 and the mirroring goes center - ?? to center + ??
without overlapping other mirrored sections.
But the patterns require using the whole shebang input of; both composites and primes.
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ dodicat.
Here is a gcd by factorisation.
How should I walk along the final two lists of factors rather than For ia, For ib rectangular search.

Code: Select all

`'=======================================================================' Factorise a 64 bit Unsigned Long Integer'=======================================================================Type factor_table               ' 216 bytes = 8 + 8*16 + 4*16 + 4 + 8     number As Ulongint          ' the input number to factorise    prime(0 To 15) As Ulongint  ' prime factors found, maximum possible = 15    count(0 To 15) As Integer   ' repeat count for each prime factor found    nf As Integer               ' the number of different prime factors found    seconds As Double           ' time in seconds used for the factorisationEnd TypeDeclare Sub Show_factors(Byref As factor_table)Declare Sub factors(     Byref As factor_table)'=======================================================================' find GCD using factor tables'=======================================================================Randomize Timer * 1e6Dim As factor_table a, b    ' object to hold input and outputsa.number = Rnd * 100 + 1000factors(a)show_factors(a)b.number = Rnd * 100 + 1000factors(b)show_factors(b)Dim As Integer count, gcd = 1For ia As Integer = 1 To a.nf    For ib As Integer = 1 To b.nf        If a.prime(ia) = b.prime(ib) Then            count = a.count(ia)            If b.count(ib) < count Then count = b.count(ib)             For i As Integer = 1 To count                gcd *= a.prime(ia)            Next i        End If    Next ibNext iaPrint " GCD ="; gcdPrint "              All done."'=======================================================================' macro used by factorisation routine'=======================================================================#macro divisor_step(skip)   ' test if this trial divisor is a factor of numberdivisor += skipDo    residue = num Mod divisor   ' remainder of this trial division    If residue = 0 Then         ' a factor has been found        If .prime(.nf) = divisor Then  ' previous prime factor repeats            .count(.nf) += 1        Else                    ' a new factor has been found            .nf += 1            ' initiate a new factor entry            .prime(.nf) = divisor            .count(.nf) = 1        End If        num = num \ divisor     ' remove the factor        limit = Sqr(num)        ' move the limit down    End IfLoop Until residue <> 0         ' finished repeats of this divisor#endmacro'=======================================================================' factorisation routine'=======================================================================Sub factors( Byref table As factor_table )    With table        .seconds = Timer        .nf = 0   ' number of different factors found so far        Dim As Ulongint num = .number, residue        Dim As Ulongint divisor = 0, limit = Sqr(num)        ' start with the silly test        If num < 2 Then     ' zero and one default here to prime because,            .nf = 1         '  they have only one entry in the table,            .count(1) = 1   '   they have a count of one, and that one            .prime(1) = num '    factor's value is equal to the number.            .seconds = 0        Else            ' then small prime divisors            divisor_step(2)  ' test  2            divisor_step(1)  ' test  3            divisor_step(2)  ' test  5            divisor_step(2)  ' test  7            Do  ' then full ahead with a repeat cycle of ( 2 * 3 * 5 ) = 30                divisor_step(4)   ' 11   41   71   101   131 note:                divisor_step(2)   ' 13   43   73   103   133  that                divisor_step(4)   ' 17   47   77   107   137  each                divisor_step(2)   ' 19   49   79   109   139  column                divisor_step(4)   ' 23   53   83   113   143  rises by                divisor_step(6)   ' 29   59   89   119   149  the repeat                divisor_step(2)   ' 31   61   91   121   151  cycle's period                divisor_step(6)   ' 37   67   97   127   157  of thirty                  ' check once every cycle of 30 to detect number is a prime                 If divisor > limit Then ' the number remaining must be prime                    If num > 1 Then                        .nf += 1                        .prime(.nf) = num                        .count(.nf) = 1                    End If                    Exit Do                End If            Loop Until num = 1            .seconds = Timer - .seconds        End If    End WithEnd Sub'=======================================================================' display the list of factors found'=======================================================================Sub Show_factors(Byref table As factor_table)    With table        Print .number; " = ";         For i As Integer = 1 To .nf            If i > 1 Then Print " x ";             Print .prime(i);            If .count(i) > 1 Then Print "^" & .count(i);        Next i        If (.nf = 1) And (.count(1) = 1)  Then            Color 13 : Print " is prime. "; : Color 7        End If    End With    PrintEnd Sub'=======================================================================Sleep'=======================================================================`
dodicat
Posts: 6628
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

Richard/Albert
I've tried various methods myself to elegantize the intersection of two sets of numbers.
Pascal and other languages have some SET functions inbuilt.
I tried using the bubblesort algo where every element comes into contact with every element in a single array - extended to two arrays, I was nearly there at one stage.
Unions and intersections and other SET operations would be a little project worth fiddelling with in FreeBASIC, maybe it's been done somewhere in the forum already?

The next step to perform is getting all factors of a number from prime factors of a number.
With say N prime factors 2^N -1 combinations would be possible - (~ I RECKON) - but some of these could well be duplicates and would have to be weeded out.

Anyway, I've updated my own HCF of two or more numbers, using prime factors. I think they call something like this PROCRASTINATION.

The LCM of numbers within ulongint can very quickly go out of bounds, so I've tentatively just used a double for this.

Code: Select all

` Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer    Dim As Integer i    #macro fill(x)    i=Ubound(p)+1    Redim Preserve p(1 To i)    p(i)=x    #endmacro    #macro Eliminate(x)    While number Mod x=0        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1    Wend    #endmacro    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull        Eliminate(2)    Eliminate(3)        While divisor<limit        divisor=divisor+6         Eliminate((divisor-1))        Eliminate((divisor+1))    Wend    If number>1 Then         fill(number)        check=check*number    End If    number=original    Return check=originalEnd FunctionSub PrintPrimeFactors(factors() As Ulongint)    Var msg=", ",acc=1ull    Print    For z As Integer=1 To Ubound(factors)        If z<Ubound(factors) Then msg=", " Else msg=""        acc=acc*factors(z)        Print factors(z) & msg;    Next z    Print     If Ubound(factors)=1 Then msg=" (Number is a PRIME)"    Print "Prime factors of " & acc & msg:Print "______":PrintEnd SubDim Shared As Integer startFunction IsIn(a() As Ulongint,num As Ulongint)As Integer    For x1 As Integer=start+1 To Ubound(a)        If num=a(x1) Then start=x1:Return -1    Next x1End FunctionFunction hcf(num1 as Ulongint,num2 As Ulongint) As Ulongint    redim as ulongint a1(),a2()    getprimefactors(num1,a1())    getprimefactors(num2,a2())    Dim As Ulongint prod=1    For x1 As Integer=1 To Ubound(a1)        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)    Next x1    start=0    Return prodEnd Function' ============================================================dim as ulongint number,x',lcm 'optional ulongint or double for lcmdim as double lcmPrint "More than two numbers if required, enter 0 to end inputs"printinput "FIRST NUMBER ";numberlcm=numberdo    input " Next number ";x    if x>0 then        number=hcf(number,x)        lcm=lcm*(x\hcf(lcm,x))    end ifloop until x=0printprint "HCF = ";numberprint "LCM = ";lcmprint "-------- Press a key --------------------------------"sleep'========================================='OR JUST FOR HCF OF TWO NUMBERS ----dim as ulongint n1,n2,gcdredim as ulongint f1(),f2(),f3()n1=56778855490064n2=6677554440024if GetPrimeFactors(n1,f1()) then PrintPrimeFactors(f1())if GetPrimeFactors(n2,f2()) then PrintPrimeFactors(f2())gcd=hcf(n1,n2)print "HCF of ";n1;" and ";n2;" = ";gcdif GetPrimeFactors(gcd,f3()) then PrintPrimeFactors(f3())sleep `
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ dodicat.
I think I solved it. Since my prime factor lists are already sorted it turns out that it is easy to walk the walk.
dodicat wrote:The LCM of numbers within ulongint can very quickly go out of bounds
By using Ulongint for the GCD there should be no overflow when building the GCD of two Ulongint numbers. It must be smaller than or equal to the smaller of the input numbers.
Here is my revised code.

Code: Select all

`'=======================================================================' Find GCD from Factors. '=======================================================================Type factor_table               ' 216 bytes = 8 + 8*16 + 4*16 + 4 + 8     number As Ulongint          ' the input number to factorise    prime(0 To 15) As Ulongint  ' prime factors found, maximum possible = 15    count(0 To 15) As Integer   ' repeat count for each prime factor found    nf As Integer               ' the number of different prime factors found    seconds As Double           ' time in seconds used for the factorisationEnd TypeDeclare Sub      factors(Byref As factor_table)Declare Sub Show_factors(Byref As factor_table)'=======================================================================' find GCD using factor tables'=======================================================================Randomize Timer * 1e6Dim As factor_table a, b    ' object to hold input and outputsa.number = Rnd * 100 + 1000factors(a)show_factors(a)b.number = Rnd * 100 + 1000factors(b)show_factors(b)Dim As Ulongint gcd = 1Dim As Integer count, ia = 1, ib = 1Do    If a.prime(ia) = b.prime(ib) Then        count = a.count(ia)        If b.count(ib) < count Then count = b.count(ib)         For i As Integer = 1 To count            gcd *= a.prime(ia)        Next i        ia += 1        ib += 1    Else        If a.prime(ia) < b.prime(ib) Then            ia += 1        Else            ib += 1        End If    End IfLoop Until (ia > a.nf) Or (ib > b.nf)Print " GCD = "; gcdPrint "              All done."'=======================================================================' Factorise a 64 bit Unsigned Long Integer'=======================================================================' macro used by factorisation routine'=======================================================================#macro divisor_step(skip)   ' test if this trial divisor is a factor of numberdivisor += skipDo    residue = num Mod divisor   ' remainder of this trial division    If residue = 0 Then         ' a factor has been found        If .prime(.nf) = divisor Then  ' previous prime factor repeats            .count(.nf) += 1        Else                    ' a new factor has been found            .nf += 1            ' initiate a new factor entry            .prime(.nf) = divisor            .count(.nf) = 1        End If        num = num \ divisor     ' remove the factor        limit = Sqr(num)        ' move the limit down    End IfLoop Until residue <> 0         ' finished repeats of this divisor#endmacro'=======================================================================' factorisation routine'=======================================================================Sub factors( Byref table As factor_table )    With table        .seconds = Timer        .nf = 0   ' number of different factors found so far        Dim As Ulongint num = .number, residue        Dim As Ulongint divisor = 0, limit = Sqr(num)        ' start with the silly test        If num < 2 Then     ' zero and one default here to prime because,            .nf = 1         '  they have only one entry in the table,            .count(1) = 1   '   they have a count of one, and that one            .prime(1) = num '    factor's value is equal to the number.            .seconds = 0        Else            ' then small prime divisors            divisor_step(2)  ' test  2            divisor_step(1)  ' test  3            divisor_step(2)  ' test  5            divisor_step(2)  ' test  7            Do  ' then full ahead with a repeat cycle of ( 2 * 3 * 5 ) = 30                divisor_step(4)   ' 11   41   71   101   131 note:                divisor_step(2)   ' 13   43   73   103   133  that                divisor_step(4)   ' 17   47   77   107   137  each                divisor_step(2)   ' 19   49   79   109   139  column                divisor_step(4)   ' 23   53   83   113   143  rises by                divisor_step(6)   ' 29   59   89   119   149  the repeat                divisor_step(2)   ' 31   61   91   121   151  cycle's period                divisor_step(6)   ' 37   67   97   127   157  of thirty                  ' check once every cycle of 30 to detect number is a prime                 If divisor > limit Then ' the number remaining must be prime                    If num > 1 Then                        .nf += 1                        .prime(.nf) = num                        .count(.nf) = 1                    End If                    Exit Do                End If            Loop Until num = 1            .seconds = Timer - .seconds        End If    End WithEnd Sub'=======================================================================' display the list of factors found'=======================================================================Sub Show_factors(Byref table As factor_table)    With table        Print .number; " = ";         For i As Integer = 1 To .nf            If i > 1 Then Print " x ";             Print .prime(i);            If .count(i) > 1 Then Print "^" & .count(i);        Next i        If (.nf = 1) And (.count(1) = 1)  Then            Print " is prime. ";        End If    End With    PrintEnd Sub'=======================================================================Sleep'=======================================================================`
albert
Posts: 5884
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

What code are you guys using to find Primes now??

=======================================================================================
Mine is still doing divisions up to the value.
I'll stick your guys's faster code into my pattern searcher, instead of pulling the Primes from a file.
=======================================================================================

If it pans out, you'll be able to say that :

"NumX" is in the "Nth" pattern and that pattern centers at "Y" and goes "+- N" and follows formula "F_n"

It seems that the primes and composites together, make a map fold, accordian type , of mirroring,
Where you have a center at a peak and it mirrors on the other side of the fold.
But some of the folds seems to be differing sizes???
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ Albert.
I use this prime finder code. Set the maximum nmax to trade number of primes with time.

Code: Select all

`'=======================================================================' Pretty Fast "Sieve of Eratosthenes" Prime Generator' the primes found are saved in primes(1 to np)' for the range from 2 to nmax, where nmax has a maximum of about 10^8' nMax       np     time       prime %'   10        4      2 usec     40.0'  100       25      4 usec     25.0'   1k      168     19 usec     16.8'  10k     1229    180 usec     12.29' 100k     9592    2.2 msec      9.59'   1M    78498     28 msec      7.84'  10M   664579    335 msec      6.65' 100M  5761455    3.7 sec       5.76''=======================================================================Dim Shared As Integer nmax = 12750 '1e2    ' the range maximum numberDim Shared As Integer np    ' the number of primes found that are <= nmaxRedim Shared As Integer primes(0 To nmax) ' final size is primes(1 to np)'-----------------------------------------------------------------------Sub generate_primes    np = 0    Dim As Integer i, k    For k = 2 To nmax        If primes(k) = 0 Then            np += 1            primes(np) = k            For i = 2*k To nmax Step k                primes(i) = 1            Next i        End If    Next k    Redim Preserve primes(np)End Sub'-----------------------------------------------------------------------' test the sub Dim As Double t = Timergenerate_primest = Timer - tPrint np; " primes found up to"; nmax;Print Using " in###.###### seconds."; t' display only the largest 100 foundDim As Integer first = np - 100If first < 1 Then first = 1For i As Integer = first To np    Print primes(i),Next i'=======================================================================Print " All done."Sleep'=======================================================================`
albert
Posts: 5884
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
Thanks !! Thats alot faster than all the divisions.
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

And it is not even an optimised version!