A different and better way to find prime numbers

[DrV]

The modulus, or remainder, operator divides number1 by number2 (rounding floating-point numbers to integers) and returns only the remainder as result

I assume it's the same for QB - but that's pretty vague on what rounding to integer means... does it round floating-point values to an integer that is still stored in a floating-point representation, or does it round to integer and convert to an integer type? I would assume it is the latter (convert to integer type) because of the fact that 2,147,483,647 is the highest possible value - this is also the largest positive value a signed 4-byte integer (LONG) can hold.

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.

I also did a test and an overflow only occurred with the value 2,147,483,648, not 2,147,483,647.

Code:

DIM a AS DOUBLE, b AS DOUBLE, c AS DOUBLE
a = 2147483647#
b = 2147483647#
c = a MOD b
PRINT c

Interchanging 'a' or 'b' for any values less than or equal to 2,147,483,647 does not cause an overflow.

[Moneo]

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.

Yes, you can use DOUBLEs, but they can only go up to the limit of a LONG.
*****

[Moneo]

..... I also did a test and an overflow only occurred with the value 2,147,483,648, not 2,147,483,647 .....

Your analysis of the "rounding floating point numbers to integers" seems to be correct. Why doesn't the documentation just say rounded to a LONG integer instead of pussy-footing with the wording?

Anyway, whether the max value that I tested is 1 off from your experience, does not seem to matter much. The point is that the max is directly related to the max of the LONG, regardless what the variable is defined as.

Thanks for getting involved and shedding some light on the subject.
*****

[Mango]

Sorry to say this, but...your method is basically the most naive method available. It suffers some major flaws. First...you test even numbers...a mistake. second, you test multiples of three (other than three itself...a major mistake). Third...you test multiples of five (other than five itself...a major mistake). Fourth...you test multiples of seven (other than seven itself...a major mistake)....all of which makes for a slower algorithm than one that doesn't. also...the suggestion to only test up to the square-root of the number makes good sense. a couple of yrs ago, Neo and I posted some code that was fairly well optimized for finding primes...there are still better methods...however, if you use your method to find all primes starting with 3, you will quickly find that your alg. is basically the slowest possible, unless, you use division with an IF statement instead of the MOD operator.

Not trying to discourage...just trying to point you towards faster methods.

Cheers.

[rpgfan3233]

Here's a prime number generator that I created a couple of months ago:
[syntax="QBasic"]DEFLNG I, X
DEFINT P
CLS
INPUT "Enter a number: ", i
prime = 1
FOR x = FIX(SQR(i) + SGN(SQR(i)) * .5) TO 1 STEP -1
IF i > 1 THEN
IF (i MOD x = 0) AND (x <> 1) THEN
prime = 0
EXIT FOR
END IF
ELSE
prime = 0
EXIT FOR
END IF
NEXT
PRINT LTRIM$(STR$(i)) + " is ";
IF prime <> 1 THEN PRINT "not ";
PRINT "prime"[/syntax]
Don't question it, just enjoy it. :-P

[Moneo]

Hey guys,

The subject of this thread is determining prime numbers. This may sound strange to some of you, but in 44 years of programming I have never had to work with prime numbers.

Could some of you give me a practical application or some examples where you need to work with prime numbers. Just curious.
*****

[Sterling Christensen]

Could some of you give me a practical application or some examples where you need to work with prime numbers. Just curious.

Encryption

Ladies and gentlemen, introducing the latest internet innovation: E-cryption :oops:

[rpgfan3233]

Ecryption

Encryption? A good idea, but how would you differentiate between prime numbers, such as 23 VS 233? Would numbers with less than 4 digits be converted to 4-digit numbers using zeroes for padding or something (I do that for octal and hexadecimal usually)?

[Sterling Christensen]

Ecryption

Encryption? A good idea, but how would you differentiate between prime numbers, such as 23 VS 233? Would numbers with less than 4 digits be converted to 4-digit numbers using zeroes for padding or something (I do that for octal and hexadecimal usually)?

I dunno how it works... I just know most modern encryption techniques use prime numbers.

[rpgfan3233]

I dunno how it works... I just know must modern encryption techniques use prime numbers.

Really? I always thought encryption was mainly 64-bit and 128-bit nowadays. I guess that shows my (lack of) knowledge of encryption techniques. :-P