lofac

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
dafhi
Posts: 1200
Joined: Jun 04, 2005 9:51

lofac

Postby dafhi » Jun 15, 2018 1:36

2018 June 16 - updated with comments.

Code: Select all

'"lofac" is my own invention.  The function returns the lowest factor.
inspired by https://en.wikipedia.org/wiki/Primality_test

type myint as integer

function lofac(i as myint) as myint
  if i<4 then return 1
  if (i and 1)=0 then return 2
  var n=3
  while n*n <= i
    if i mod n = 0 then return n
    n += 2
  Wend
  return 1
End Function

for i as long = 2 to 99
  if lofac(i)=1 then ? i; " ";
Next

?
?
? lofac(57)

sleep

for a fast primality test, see post by frisian
Last edited by dafhi on Jun 16, 2018 14:12, edited 5 times in total.
counting_pine
Site Admin
Posts: 5956
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: lofac

Postby counting_pine » Jun 15, 2018 13:27

You forgot to explain to us what lofac is or does.
Everyone reading the thread or just seeing the title will be a bit confused.
Something to do with factors, I'm guessing?

EDIT: Thanks.
:-)
Imortis
Posts: 1572
Joined: Jun 02, 2005 15:10
Location: USA
Contact:

Re: lofac

Postby Imortis » Jun 15, 2018 17:06

counting_pine wrote:...Everyone reading the thread or just seeing the title will be a bit confused...


Yeah, I tried to google it and found nothing that looks relevant.
deltarho[1859]
Posts: 1573
Joined: Jan 02, 2017 0:34
Location: UK

Re: lofac

Postby deltarho[1859] » Jun 15, 2018 17:24

According to the WiKi leak it is a Primality test.

You cannot beat usage examples. I often use them in my posts. They get folk up to speed faster.

lofac(12349) =>53, which tells us that 12349 is not a prime because 12349/233 = 53

lofac(29) => 1, which tells us that 29 is a prime and cannot be divided by 1 < number < 29 and still give an integer.

lofac(104729) => 1 is a prime

lofac(58439) => 1 is also a prime.

dafhi's code is also fairly swift - that last calc came back in 595 nano-seconds although at that level I'd call it less than a micro-second.
Provoni
Posts: 279
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: lofac

Postby Provoni » Jun 17, 2018 8:19

Fermat's method (not optimized):

Code: Select all

screenres 640,480,32

dim as uinteger i,n,s
dim as double d

n=12349
s=sqr(n)

do
   i+=1
   s+=1
   d=sqr((s*s)-n)
   if frac(d)=0 then
      print "iterations: "+str(i)+", "+str(s-d)+" * "+str(s+d)+" = "+str(n)
      exit do
   end if
loop

beep
sleep

It can be used in junction with trial division to speed it up.

How it works? Say you have the number 21. Take the next square that comes after 21. It is 25, 5*5. Get the difference between 21 and 25, that is 4. It is also a square 2*2. The factorization then is (5-2)*(5+2)=21. If the difference between 21 and 25 is not a square then try the next square (6*6=36) and so on.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest