lofac

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
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_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
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
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,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.