Prime Factors

[SMcNeill]

Code: (Select All)

ReDim PF(0) As Long
ReDim Shared As Long Prime_Factors(1 To 168)
Screen _NewImage(1280, 900, 32)
_Delay .5
_ScreenMove _Middle

Init

Do
    Input "Give me a number from 1 to 1016064 (0 quits) =>"; num
    If num <= 0 Or num >= 1016064 Then System
    GetPF num, PF()
    For i = 0 To UBound(PF)
        Print PF(i);
    Next
    Print
Loop


Sub GetPF (num, PF() As Long)
    ReDim PF(1000) As Long
    If num < 1 _Orelse num > 1016064 Then Exit Sub
    limit = Int(Sqr(num))
    PF(0) = 1
    If num > 1 Then
        count = 1
        Do
            factor_on = 0
            Do
                factor_on = factor_on + 1
                temp = Prime_Factors(factor_on)
                If IsPrime(num) Then
                    PF(count) = num
                    finished = -1
                    Exit Do
                ElseIf num Mod temp = 0 Then
                    PF(count) = temp
                    count = count + 1
                    num = num \ temp
                    Exit Do
                End If
            Loop
        Loop Until finished
    End If
    ReDim _Preserve PF(count) As Long
End Sub






Function IsPrime (num)
    'to check for any given number less than 1,016,064, we only have to do a maximum of 170 comparisons
    'as the max value we ever have to check against is the SQR of our number.
    'for example, no value higher than 10 could ever be a factor in 100 and be prime!
    'so for numbers less than 1,000,000, all we need do is compare them against factors less than 1,000.
    'and there's not that many of them, as you can see below!
    If num < 2 _Orelse num > 1016064 Then Exit Function
    Static As Long Prime_Array_Init, Factor_Count(1 To 10)
    Dim As Long factor_on, i, j, factor
    If Prime_Array_Init = 0 Then
        Prime_Array_Init = -1
        Restore Prime_Factor_Count
        For i = 1 To 10: Read Factor_Count(i): Next

    End If

    IsPrime = -1
    For j = 1 To 10 'broken down to give 10 quick exit points so we don't check every value for an answer.
        For i = 1 To Factor_Count(j)
            factor_on = factor_on + 1
            factor = Prime_Factors(factor_on)
            If num <= factor Then
                Exit Function
            Else
                If num Mod factor = 0 Then IsPrime = 0: Exit Function
            End If
        Next
        If num < factor * factor Then Exit Function
    Next

    Exit Function
    Prime_Factor_Count: 'each value here represents the number of prime factors in number increments of 100
    'for example, there are 25 prime numbers between 1 and 100, 21 primes between 101 and 200, ect...
    Data 25,21,16,16,17,14,16,14,15,14
End Function

Sub Init
    Restore prime_data:
    For i = 1 To 168: Read Prime_Factors(i): Next
    Exit Sub
    prime_data:
    Data 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97: 'factors up to 10,000 (100 ^ 2)
    Data 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199: 'up to 44,100 (210 ^ 2)
    Data 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293: 'up to 93,636 (306 ^ 2)
    Data 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397: 'up to 160,000 (400 ^ 2)
    Data 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499: 'up to 252,004 (502 ^ 2)
    Data 503,509,521,523,541,547,557,563,569,571,577,587,593,599: 'up to 360,000 (600 ^ 2)
    Data 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691: 'up to 490,000 (700 ^ 2)
    Data 701,709,719,727,733,739,743,751,757,761,769,773,787,797: 'up to 652,864 (808 ^ 2)
    Data 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887: 'up to 820,836 (906 ^ 2)
    Data 907,911,919,929,937,941,947,953,967,971,977,983,991,997: 'up to 1,01,064 (1008 ^ 2)


End Sub

Building upon the IsPrime function, we now have a means to break a number down into its prime factors.

For example:

12 = 2 * 2 * 3
124 = 2 * 2 * 31

---

Next step for what I'm working on and playing around with will be fraction simplification.

Take a value like 12 / 16... that can simplify down to 3 / 4. This should now have me on the route to do that easily.

(Break the nominator (top number) down to its prime factors. Check those values against the denominator (bottom number). If they divide evenly (mod = 0) then reduce both numbers by that factor.)

[PhilOfPerth]

Code: (Select All)

ReDim PF(0) As Long
ReDim Shared As Long Prime_Factors(1 To 168)
Screen _NewImage(1280, 900, 32)
_Delay .5
_ScreenMove _Middle

Init

Do
    Input "Give me a number from 1 to 1016064 (0 quits) =>"; num
    If num <= 0 Or num >= 1016064 Then System
    GetPF num, PF()
    For i = 0 To UBound(PF)
        Print PF(i);
    Next
    Print
Loop


Sub GetPF (num, PF() As Long)
    ReDim PF(1000) As Long
    If num < 1 _Orelse num > 1016064 Then Exit Sub
    limit = Int(Sqr(num))
    PF(0) = 1
    If num > 1 Then
        count = 1
        Do
            factor_on = 0
            Do
                factor_on = factor_on + 1
                temp = Prime_Factors(factor_on)
                If IsPrime(num) Then
                    PF(count) = num
                    finished = -1
                    Exit Do
                ElseIf num Mod temp = 0 Then
                    PF(count) = temp
                    count = count + 1
                    num = num \ temp
                    Exit Do
                End If
            Loop
        Loop Until finished
    End If
    ReDim _Preserve PF(count) As Long
End Sub






Function IsPrime (num)
    'to check for any given number less than 1,016,064, we only have to do a maximum of 170 comparisons
    'as the max value we ever have to check against is the SQR of our number.
    'for example, no value higher than 10 could ever be a factor in 100 and be prime!
    'so for numbers less than 1,000,000, all we need do is compare them against factors less than 1,000.
    'and there's not that many of them, as you can see below!
    If num < 2 _Orelse num > 1016064 Then Exit Function
    Static As Long Prime_Array_Init, Factor_Count(1 To 10)
    Dim As Long factor_on, i, j, factor
    If Prime_Array_Init = 0 Then
        Prime_Array_Init = -1
        Restore Prime_Factor_Count
        For i = 1 To 10: Read Factor_Count(i): Next

    End If

    IsPrime = -1
    For j = 1 To 10 'broken down to give 10 quick exit points so we don't check every value for an answer.
        For i = 1 To Factor_Count(j)
            factor_on = factor_on + 1
            factor = Prime_Factors(factor_on)
            If num <= factor Then
                Exit Function
            Else
                If num Mod factor = 0 Then IsPrime = 0: Exit Function
            End If
        Next
        If num < factor * factor Then Exit Function
    Next

    Exit Function
    Prime_Factor_Count: 'each value here represents the number of prime factors in number increments of 100
    'for example, there are 25 prime numbers between 1 and 100, 21 primes between 101 and 200, ect...
    Data 25,21,16,16,17,14,16,14,15,14
End Function

Sub Init
    Restore prime_data:
    For i = 1 To 168: Read Prime_Factors(i): Next
    Exit Sub
    prime_data:
    Data 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97: 'factors up to 10,000 (100 ^ 2)
    Data 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199: 'up to 44,100 (210 ^ 2)
    Data 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293: 'up to 93,636 (306 ^ 2)
    Data 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397: 'up to 160,000 (400 ^ 2)
    Data 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499: 'up to 252,004 (502 ^ 2)
    Data 503,509,521,523,541,547,557,563,569,571,577,587,593,599: 'up to 360,000 (600 ^ 2)
    Data 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691: 'up to 490,000 (700 ^ 2)
    Data 701,709,719,727,733,739,743,751,757,761,769,773,787,797: 'up to 652,864 (808 ^ 2)
    Data 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887: 'up to 820,836 (906 ^ 2)
    Data 907,911,919,929,937,941,947,953,967,971,977,983,991,997: 'up to 1,01,064 (1008 ^ 2)


End Sub

Building upon the IsPrime function, we now have a means to break a number down into its prime factors.

For example:

12 = 2 * 2 * 3
124 = 2 * 2 * 31

---

Next step for what I'm working on and playing around with will be fraction simplification.

Take a value like 12 / 16...  that can simplify down to 3 / 4.  This should now have me on the route to do that easily. 

(Break the nominator (top number) down to its prime factors.  Check those values against the denominator (bottom number).  If they divide evenly (mod = 0) then reduce both numbers by that factor.)

Nice! Wish I could do that!  

[Jack]

@SMcNeill
on another forum someone asked about how to factor large integers, say 70 digits in a fast way
suppose that you have big integer type at your disposal, how would you implement a fast factorization program ?

[Pete]

Greatest Common Factor. I made one for my String Math routine.

https://qb64phoenix.com/forum/showthread...36#pid5236

I'm not sure if it is the most recent. I recall making some modifications in my compare routine either before or after this post.

Pete

[Jack]

thanks Pete, will try it in a while
I found some entries on the Rosetta Code https://rosettacode.org/wiki/Prime_decomposition
I tried the FreeBasic implementation because there's an easy to use GMP header for BigInt and changing the code from integer to BigInt is trivial
but as I was playing with it I found that some integers are easy to factorize while others are hard, for example
factor(314159265358979323846264338327950288419716939937510582097) took less than a second, but
factor(31415926535897932384626433832795028841971693993751058209749) is still running
even the pari/gp calculator took 1.6 seconds
by the way, the factors for the last one are 3, 37, 65665363877655791, 4310131680920695304618177764671198362549

[SMcNeill]

I guess the way I'd have to do such large numbers would be with string math, and then I'd cross my fingers and hope that some of the simplest tricks to math helped reduce those figures down as much as possible.

Is it an even number?   End in 2/4/6/8/0?  That can be halved and hopefully reduce the work load before you get into the hard crunch.
Can you add up the sum of the digits and evenly divide them by 3?
Does it end in 5?

Three quick and easy tests that you can do without having to worry much about string math, and it resolves a whole boat load of possibilities for you right off the bat.  (you simplify all numbers that end with 2/4/5/6/8/0 down really quickly, along with any divisible by 3.)

After that, it's just string math and let it grind until there's no grinding left to do.  Hopefully, you have a nice list of primes to go by for as much of that math as possible.   After you use up your predefined stuff, the rest is just calculating every value that remains and then it REALLY bogs down in performance.

[Jack]

thanks Steve, the questions you proposed are something to think about
this looks interesting http://en.wikipedia.org/wiki/Quadratic_sieve

[eoredson]

I wrote a factorialization function here:

Code: (Select All)

Print "Enter range";
Input p: p = Int(p)
If p <= 1 Then End
z = 2
Print " 2= (prime)" ' first prime is 2
Do Until z = p ' display factored numbers
  x$ = InKey$
  If x$ = Chr$(27) Then
      End
  End If
  z = z + 1
  x = z
  Print x; "=";
  l = 1
  q = 0
  Do Until x = 1
      l = l + 1
      Do While x / l = x \ l ' continue to divide number
        q = q + 1
        If q > 1 Then
            Print "*";
        End If
        Print l;
        x = x / l
      Loop
      If l > Int(z / 2) Then ' test for maximum divisor
        Exit Do
      End If
      If l > Int(Sqr(x)) Then ' test maximum divisor is prime
        If q = 0 Then
            Exit Do
        End If
      End If
  Loop
  If q = 0 Then ' display number is prime
      Print " (prime)";
  End If
  Print
Loop

[Jack]

thanks eoredson 
that is fine for small integers but that method is not practical for 70 digit integers, there may be cases where that would work but in general it's not practical

[SMcNeill]

thanks eoredson 
that is fine for small integers but that method is not practical for 70 digit integers, there may be cases where that would work but in general it's not practical

First thing I'd check with 70 digit numbers would be:

SELECT CASE RIGHT$(STR$(num),1)
    CASE 2, 4, 6, 8, 0    '2 is a factor.  simplify by that amount
    CASE 5 '5 is a factor, simplify by that amount
    CASE ELSE  'may be a prime as all primes above 10 end in 1, 3, 7, 9
            'this case is the one where you're going to end having to your string math
            'but if it's smaller than an INT64 by the time you get to this point (which is close to 18 digits, if I remember correctly)
            'then you can just do this with normal numbers and not have to do string math
            'either way, you've managed to simplify 60% of all numbers before you ever got to this complex processing point, and that's a nice WIN
END SELECT