Prime Number detecter bug

[MythGuyDK]

I have a program that is messing with me alot. It's a program that detects whether n is a prime number or not. But it has one major bug already: it says that 8 is not prime and that 4 is prime.

Here is the code.

Code: Select all

input "Number: ",n
cls
Print "Processing... This may take a while..."
for a = 0 to int(n/2)
    if n/a = int(n/a) then sp=0 else sp = 1
    if sp = 1 then cls:goto noprime
next a
cls
Print "The number";n;" is prime. Press any key to quit."
do:loop while inkey$ = ""
end
noprime:
Print "The number";n;" is not prime. Press any key to quit."
do:loop while inkey$ = ""
end

Question one: why is it messing up like this?
Question two: how can I fix it?

[Mindless]

okay... I'm not really answering your question, but here's some code

Code: Select all

dim as integer i
for i = 0 to 99
   dim as byte p = 1
   dim as integer j
   for j = 2 to i \ 2
      if i mod j = 0 then
         print i & " is not prime (divisible by " & j & ")"
         p = 0
         exit for
      end if
   next
   if p then print i & " is prime"
   sleep 1000
next

[Skyler]

First off, starting your loop at zero will give you division by zero errors. Division by one will also give undesired results. Try starting your loop at 2, e.g.

Code: Select all

for a = 2 to int(n/2)

Also, your "sp"s are mixed up. You want it to be 1 if the expression is true, not vice versa.

[MythGuyDK]

Yeah... I just figured the 'sp's out. Thanks.

[cha0s]

Just another note, instead of 'int(x/y)', you can just do 'x \ y' '\' is the integer division operator.

Code: Select all

For a = 2 To n\2
    If n/a = n\a Then

[owen]

4 / 0= 1.#INF Int(n/a)= 1.#INF sp= 0
4 / 1= 4 Int(n/a)= 4 sp= 0
4 / 2= 2 Int(n/a)= 2 sp= 0
At this point the for next has reached it's limit of half of the number ie. 2 is half of 4. so the program exits the for next and proceeds to the next statement which is to print the number is prime.

Where as:

8 / 0= 1.#INF Int(n/a)= 1.#INF sp= 0
8 / 1= 8 Int(n/a)= 8 sp= 0
8 / 2= 4 Int(n/a)= 4 sp= 0
8 / 3= 2.666666666666667 Int(n/a)= 2 sp= 1
Here on the 4th test (testing the number 3)
8/3 = 2.6667 is not equal to 2 (the integerof 2.6), so it sets sp to 1 and exits to for next, jumping to the noprime subroutine.

Code: Select all

Input "Number: ",n
Cls
Print "Processing... This may take a while..."
For a = 0 To Int(n/2)
    If n/a = Int(n/a) Then sp=0 Else sp = 1
    Print n;" /";a;"=";n/a;" Int(n/a)=";Int(n/a);" sp=";sp
    If sp = 1 Then Goto noprime
Next a
Print "exiting For Next"

Print "The number";n;" is prime. Press any key to quit."
Do:Loop While Inkey$ = ""
End
noprime:
Print "The number";n;" is not prime. Press any key to quit."
Do:Loop While Inkey$ = ""
End

A simple example to find primes is:

The for next uses a step of 2 starting at 3 to the square root of the number to test.

For example if you were to test 121 for primality the For Next would test from 3 to 11 in steps of 2 ie. (3,5,7,9,11)

There is no need to test any higher then the square root of the number.

Code: Select all

Dim As Integer n,q

Print "Prime number test"
Input "Enter an odd number (3 or higher) ";n

For q = 3 To Int(sqr(n)) Step 2
   If n Mod q = 0 Then
      Print n; " is not prime, it is divisible by";q
      Print "press any key to end"
      Sleep
      end
   EndIf
Next

Print n; " is prime"
Print "press any key to end"
Sleep
end

[pyrodap]

and that fact cuts calculation time in half once you start getting to higher numbers...

[Antoni]

This is the way i use to factorize.
Btw, the URL I recommend for checking results has a java applet thet factorizes in a flash a 64 bits integer. The code (supplied) to achieve this speed is 9500 lines long...

Code: Select all

'factorize an integer by Antoni
'Check the results here http://www.alpertron.com.ar/ECM.HTM

dim shared as ulongint x,c

sub checkf(k as ulongint)
Dim As ULongInt x1

do
  If x Mod k <>0 Then Exit do
  x1 = x \ k
  'if x1 =1 then exit do   
  PRINT  k
  C=C*K
  x=x1
loop
end sub


dim as single t
dim as ulongint a,k,sq
do
  print
   INPUT "enter a number smaller than 1.8446 E19 to factorize[0 to end] : ", x
   If x<1 Then end
   print "Factorizing ";x
 
   t=timer
   sq=sqr(x)
   Print sq
   PRINT "the prime factors are: "
   c=1
   checkf(2ull)
   checkf(3ull)
   a=2ull
   k = 3ull + a

   WHILE K <= sq
     checkf(k)
     k = k + a
     a=6-a
   WEND
   if x>1 then print x;:c=c*x
   print: PRINT "Ended in ";timer-t;" seconds. Product of all factors: "; C
loop