Posts: 63
Threads: 15
Joined: Jul 2005
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]
Posts: 500
Threads: 7
Joined: Jun 2005
Interesting method. No directly viewable hack for when n = 2.
Very nice job! :-)
974277320612072617420666C61696C21 (Hexadecimal for those who don't know)
Posts: 1,272
Threads: 36
Joined: Feb 2003
Even better, you only have to go up to half of n. n will never be a multiple of a number > .5n
Posts: 3,522
Threads: 189
Joined: Dec 2003
Although, it's far from the fastest method..
Posts: 1,439
Threads: 15
Joined: Apr 2003
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.
Posts: 500
Threads: 7
Joined: Jun 2005
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)
Posts: 1,956
Threads: 65
Joined: Jun 2003
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.
*****
Posts: 500
Threads: 7
Joined: Jun 2005
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)
Posts: 1,956
Threads: 65
Joined: Jun 2003
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.
*****
Posts: 500
Threads: 7
Joined: Jun 2005
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)
|