## lofac

dafhi
Posts: 1251
Joined: Jun 04, 2005 9:51

### lofac

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_testtype myint as integerfunction 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 1End Functionfor 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
Posts: 6173
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: lofac

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
Moderator
Posts: 1629
Joined: Jun 02, 2005 15:10
Location: USA
Contact:

### Re: lofac

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

### Re: lofac

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: 322
Joined: Jan 05, 2014 12:33
Location: Belgium

### Re: lofac

Fermat's method (not optimized):

Code: Select all

`screenres 640,480,32dim as uinteger i,n,sdim as double dn=12349s=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 ifloopbeepsleep`

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.