Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
A different and better way to find prime numbers
#1
Why use the Sieve of Eratosthenes for finding prime numbers? There is a better, shorter, and faster way, and I figured it out on my own. Here is the code:

INPUT "Number: " , n
FOR I = 2 TO n - 1
IF n MOD I = 0 THEN PRINT "Number not prime.": END
NEXT
PRINT 'Number prime."

In case youre wondering how this works, the MOD command just returns the remainder from division. If a number is prime, then it will return all remainders, since it will not go into any number evenly. However, if it does return a remander, then it is not prime, since it is divisible by a number other than itself and 1.


Enjoy, I guess...
quote="Bruce Raeman"]Anatomy (n): something everyone has, but which looks better on a girl[/quote]
Reply
#2
Interesting method. No directly viewable hack for when n = 2.

Very nice job! :-)
974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Reply
#3
Even better, you only have to go up to half of n. n will never be a multiple of a number > .5n
Reply
#4
Although, it's far from the fastest method..
Reply
#5
Quote:Even better, you only have to go up to half of n. n will never be a multiple of a number > .5n
In fact, you only need to check up to the square root of n.
Reply
#6
Quote:In fact, you only need to check up to the square root of n.
Correct. Even better, you only need to check up to the greatest positive integer less than or equal to the square root of n (other than 1), meaning the FIX() function could be used.

[syntax="QBasic"]INPUT "Number: " , n
FOR I = 2 TO FIX(SQR(n))
IF (n MOD I = 0) OR (n < 2) THEN PRINT "Number not prime.": END
NEXT
PRINT "Number prime."[/syntax]
(1 and 0 are not considered prime numbers) ;-)
974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Reply
#7
Jake and Rpgfan,

Either of your solutions seem to work ok.

However, for some strange reason, if the input number "n" is greater than 2,147,483,647, which is the maximum value for a LONG integer, you will get an Error 06: overflow error, when the MOD instruction gets executed.

I consulted the QB Online Help plus my Quickbasic manual and there is no mention of any maximum values for the MOD operator. However, it does mention that "real" values will be rounded to integers, and this could be a clue as to why the maximum is a long integer.

So, the bottom line is that if your number is equal or greater than 2,147,483,647 then you can't use a MOD in your logic to determine if it's a prime number.
*****
Reply
#8
Quote:Jake and Rpgfan,

Either of your solutions seem to work ok.

However, for some strange reason, if the input number "n" is greater than 2,147,483,647, which is the maximum value for a LONG integer, you will get an Error 06: overflow error, when the MOD instruction gets executed.

I consulted the QB Online Help plus my Quickbasic manual and there is no mention of any maximum values for the MOD operator. However, it does mention that "real" values will be rounded to integers, and this could be a clue as to why the maximum is a long integer.

So, the bottom line is that if your number is equal or greater than 2,147,483,647 then you can't use a MOD in your logic to determine if it's a prime number.
*****
The maximum value for MOD is the maximum value of the data types of the variables (or numbers) used with it. For LONG, it is &h7FFFFFFF (the hex is easier to remember, but in decimal it is 2,147,483,647). If there was a way to use arrays, a limit wouldn't be as noticeable.
974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Reply
#9
Quote:.......The maximum value for MOD is the maximum value of the data types of the variables (or numbers) used with it. For LONG, it is &h7FFFFFFF (the hex is easier to remember, but in decimal it is 2,147,483,647). If there was a way to use arrays, a limit wouldn't be as noticeable.
Not quite.
I set up a test with the number DIMed as DOUBLE. When the input number was equal to 2,147,483,647 an overflow error was issued.
*****
Reply
#10
Quote:Not quite.
I set up a test with the number DIMed as DOUBLE. When the input number was equal to 2,147,483,647 an overflow error was issued.
*****
Hehe. . . QB gives an example using 19 MOD 6.7 = 5. I assumed DOUBLEs could be used then.
974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)