I am curious to know which of you great and powerful programmers can come up with the shortest program to check a number to see if it is prime... in BASIC! HAHAHAHAA!!! Please forgive me if it is below you or if it has been done before, but it is a good test of programming and mathematical abities (I am an ameteur mathematician).

INPUT "Enter number: ", num!
FOR i! = 1 TO num
 FOR j! = 1 TO num
   IF i! * j! = num! THEN numfactors% = numfactors% + 1
 NEXT j!
NEXT i!
IF numfactors% --> 2 THEN PRINT "Number is not prime!" ELSE PRINT "Number is prime"

There you go, wrote that in five minutes. Seven lines [addsig]

s/"(n mod f)!=0"/"not(n mod f)"

DXPROG-
That's pretty good, but it is possible to write a four-line program with a more efficient algorithm that will do the the job. (There is, of course, a trade off between size and efficiancy).
Keep it up!

Well, I don't know a whole lot of the fancy stuff (like what Yjo did). I was just doing what I knew how [addsig]

yeah, what did yjo do?

Yjo just used modulus. For any number n, if n modulus any number from 2 (divisble by 1 is still composite, because all numbers are divisible by 1) to sqrt(n) (because anything beyond that is just a multiple, and multiples are only divisible if their root is) is equal to 0, then the number is not prime.

16 mod 4 = 0
modulus gives the remainder.

Hope that was clear. I know it wasn't easy to read.

Wow, I'm thrilled. here's my effort:

INPUT "NUMBER?", N
FOR X = 2 TO SQRT(N)
IF N / X = INT(N / X) THEN PRINT "NOT PRIME"
---> :STOP
NEXT X
PRINT "PRIME"

Sorry, I was wrong. My min is 5 lines not 4. I forgot the "NEXT X"

[ This Message was edited by: welshbard482 on 2003-07-26 14:23 ]

How about the fastest program, as opposed to smallest?

Well, considering mine didn't involve any extra functions it may be faster. Of course, BASIC loops aren't know for speed either [addsig]

sorry to burst your bubble, but that particular method is kinda slow, for several reasons:
-you check combinations twice i.e. 2*3, 3*2 etc.
-you start on 1 and increase by ones (try starting on 3 and increasing by 2s, checking 2 once and ignoring its multiples)

[ This Message was edited by: welshbard482 on 2003-07-26 14:25 ]

I could also break out of the loop once it's found more than one factor.

_________________
When I got VB, i could have flown without thrusters and shot down TIE Interceptors just by spitting at them.

[ This Message was edited by: dxprog on 2003-07-27 01:25 ]

Checking even numbers only etc. will only improve the algorithm by a constant factor of time (1/2,1/4 etc.).
Since your algorithm is O(n^2), (the revised version is O(n^.5), your method would make
~ 6x10^10 more comparisons in checking the millionth prime (15485863) for example.
Go to http://mathworld.wolfram.com/PrimalityTest.html for superior algorithms for fast checking.

Quote:
On 2003-07-25 03:52, welshbard482 wrote:
DXPROG-
That's pretty good, but it is possible to write a four-line program with a more efficient algorithm that will do the the job. (There is, of course, a trade off between size and efficiancy).
Keep it up!



ok, here's my four-line program

input "Input number: ", n!
for x! = 2 to sqrt(n!)
--->if n! mod x! = 0 then print "Number is NOT prime!"
next

Niiiccceee-
That is sweet stuff man

awesome

Quote:
On 2003-07-26 11:32, welshbard482 wrote:
How about the fastest program, as opposed to smallest?


Fast? In BASIC?

I could imagine trying to do this in c, but if you want fast, try the challenge in asmbly. [addsig]

Well, in many ways BASIC and assembly are similar, so I dont imagine it'd be that different, just longer.

[ This Message was edited by: welshbard482 on 2003-10-08 22:06 ]

Congrats to welshbard482 for the siliest thing I've ever read on this forum...

The isPrime function, in 1 line of Haskell:

isPrime n = [x | x