lofac

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

lofac

Post by dafhi »

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: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: lofac

Post by counting_pine »

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

Re: lofac

Post by Imortis »

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

Re: lofac

Post by deltarho[1859] »

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

Re: lofac

Post by Provoni »

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.
Post Reply