Articles

Solved Finding out if integer is prime or not.

December 26, 2012 at 15:29:44
Specs: Windows 7

So basically the user enters an integer, then the output states if the integer is prime or not. Seems simple, but I just can't get it. At first I thought that a prime number is basically an odd number. So this was my program.

 program example (input, output);

var
x:integer;

begin
write(' enter an integer:');
readln(x);
if ( x mod 2 <> 0 ) then
writeln('prime')
else
writeln('not prime');
end.

Obviously this doesn't work for prime, more for odd numbers!

Also there is a part B where you enter a starting number and ending number and the output tells you how many primes are between the numbers. Example: for 50- 59 there are 2 primes in range.

Any help?


See More: Finding out if integer is prime or not.

Report •


#1
December 26, 2012 at 22:03:03
✔ Best Answer

If you're in the same class as allquestions, then you've covered modulo. For any given number, if that number mod any-other-number-other-than-itself-and-one = 0, then it is NOT prime. The set of numbers that needs to be validated against the given number is two (number is even or odd: it's even if mod for two is zero),
then every other number from 3 up to 1/3 of the given number (3,5,7...). No need to go farther that 1/3, because 1/2 has already been tested. If any modulo is zero, then the number fails to qualify as "prime". In lieu of modulo, you can "back-multiply":
divide the number by the test (to get "result1"), then multiply "result1" by the test giving "result2". If result2 = the number, then prime has failed (because rounding has occurred).
For best efficiency, (saves having to write the same code twice), make a subroutine to test a given input number:

SUB prime(A)
prime=A mod 2
if prime then
last=A/3
for j=3 to last step 2
if A mod j=0 then exit for
next j
if j>last then prime=1 else prime=0
end if
return

This is a simple, brute-force method. The preferred and more efficient method, google: sieve eratosthenes. (esp wiki).


Report •
Related Solutions


Ask Question