# Making an Algorithm to Check Whether a Number is a Prime Number

jbriggs444
Homework Helper
2019 Award
Code:
1-Input a nonnegative integer N
3-If N=1 go to step 11
3-If N=2 go to step 12
4-If N=3 go to step 12
5-If N>3 go to step 6
6-Let M=2
7-M=M+1
8-Calculate N/M
9-Check N/M=1 If yes go to step 12 , otherwise go to step 10
10-If remaining of N/M is 0 go to step 11 , otherwise go to step 7
11-N is not a prime number
12-N is a prime number
Try that code using 4 as an input.

Edit: I actually turned this into machine-readable code. [Somewhat cringe-worthy, but it runs]
Perl:
#!/usr/bin/perl
use strict;

my $n; my$m; my $quotient; LINE1: print "Enter a number: ";$n=<> or die "Invalid input"; chomp $n; LINE2: if ($n == 1 ) { goto LINE11 };
LINE3: if ( $n == 2 ) { goto LINE12 }; LINE4: if ($n == 3 ) { goto LINE12 };
LINE5: if ( $n > 3 ) { goto LINE6 }; LINE6:$m = 2;
LINE7: $m =$m + 1;
LINE8: $quotient = int ($n / $m ); LINE9: if ($quotient == 1 ) { goto LINE12 } else { goto LINE10 };
LINE10: if ( $n - ($quotient*$m ) == 0 ) { goto LINE11 } else { goto LINE7 }; LINE11: print "That number is not prime\n"; exit; LINE12: print "That number is prime\n"; exit; C:\Users\John\Documents>perl prime.pl Enter a number: 1 That number is not prime C:\Users\John\Documents>perl prime.pl Enter a number: 2 That number is prime C:\Users\John\Documents>perl prime.pl Enter a number: 3 That number is prime C:\Users\John\Documents>perl prime.pl Enter a number: 4 That number is prime C:\Users\John\Documents>perl prime.pl Enter a number: 5 That number is prime C:\Users\John\Documents>perl prime.pl Enter a number: 6 That number is not prime Last edited: • PeroK and Arman777 Gold Member Try that code using 4 as an input. Edit: I actually turned this into machine-readable code. [Somewhat cringe-worthy, but it runs] Perl: #!/usr/bin/perl use strict; my$n; my $m; my$quotient;

LINE1: print "Enter a number: "; $n=<> or die "Invalid input"; chomp$n;
LINE2: if ( $n == 1 ) { goto LINE11 }; LINE3: if ($n == 2 ) { goto LINE12 };
LINE4: if ( $n == 3 ) { goto LINE12 }; LINE5: if ($n > 3 ) { goto LINE6 };
LINE6: $m = 2; LINE7:$m = $m + 1; LINE8:$quotient = int ( $n /$m );
LINE9: if ( $quotient == 1 ) { goto LINE12 } else { goto LINE10 }; LINE10: if ($n - ( $quotient*$m ) == 0 ) { goto LINE11 } else { goto LINE7 };
LINE11: print "That number is not prime\n"; exit;
LINE12: print "That number is prime\n"; exit;
C:\Users\John\Documents>perl prime.pl
Enter a number: 1
That number is not prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 2
That number is prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 3
That number is prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 4
That number is prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 5
That number is prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 6
That number is not prime
Really nice thanks, Is it works when its like 28, 29 ? Or when its 3 digit number ?

jbriggs444
Homework Helper
2019 Award
Really nice thanks, Is it works when its like 28, 29 ? Or when its 3 digit number ?
C:\Users\John\Documents>perl prime.pl
Enter a number: 12345
That number is not prime

C:\Users\John\Documents>perl prime.pl
Enter a number: 12347
That number is prime
If you have a bug, fix it, don't paper over it! What is the crucial oversight in your code that allows this mistake to happen?

Hint: step through the execution for n = 4 and it should become obvious.

Try that code using 4 as an input.

Edit: I actually turned this into machine-readable code. [Somewhat cringe-worthy, but it runs]
What an ugly mess. This can be done much more elegantly without any line numbers or goto's. I'm sure the computer science teacher will be very happy with it. Code:
int main() {

int p = 1;
int m, n;

while (p > 0) {
if (p == 1) { cin >> n; }
else if (p == 2) { if (n == 1) { p = 9; } }
else if (p == 3) { if (n == 2) { p = 11; } }
else if (p == 4) { if (n == 3) { p = 11; } }
else if (p == 5) { m = 1; }
else if (p == 6) { m = m + 1; }
else if (p == 7) { if (n % m == 0) { p = 9; } }
else if (p == 8) { if (m*m > n) { p = 11; } }
else if (p == 9) { p = 5; }
else if (p == 10) { cout << "NOT PRIME"; }
else if (p == 11) { p = -1; }
else if (p == 12) { cout << "PRIME"; }
else if (p == 13) { p = -1; }
else cout << "Something wonderful has happened!";
p = p + 1;
}
}
if you replace the check of n/m == 1 with m*m > n at the end of the loop it still can test anything that fits in a 32 bit number without any noticeable time delay.

jbriggs444
Homework Helper
2019 Award
if you replace the check of n/m == 1 with m*m > n at the end of the loop it still can test anything that fits in a 32 bit number without any noticeable time delay.
One step at a time. We're still trying to get @Arman777 to take care of the bug on lines 6 and 7.

• Arman777
Gold Member
I couldnt test it cause the class was in the early morning. But my teacher excepted it so Idk it caused no problem.But for today I have to make 2 more flowcharts...

I couldnt test it cause the class was in the early morning. But my teacher excepted it so Idk it caused no problem.But for today I have to make 2 more flowcharts...
It's rather sad if the flowcharts you have to write are a lot less clear than the computer program would be. In this case you really want it to be clear in your program for wich values of m the trial division is done. if you have
Python:
for m in range (2, n/2):
Code:
for (m=2; m<= n/2; m++)
that should be clear enough. With your pseudocode, or with a flowchart it's not so clear exactly what values of m are used.
That seems to be the origin of the bug here. It will also make it harder to see that the program can easily be much more efficient.
If you really have to make flowcharts, i would recommend to make and test a correct program first, and then produce a flowchart. It should be easy enough to learn how to put a for, while or if into a flowchart. The flowchart will be no help with making a program unless you want to avoid any higher level code structures.

Gold Member
If you really have to make flowcharts, i would recommend to make and test a correct program first,
I dont know ho to write a program we didnt learn about it..But I see your point in general and you are right. Maybe yeah it was the problem. So now I have to create a flowchart to calculate a gcd for two positive integers.

Our flowcharts are rather simple things..thats how we are doing in class..

Gold Member
I have also questions for my other flowchart..I ll open another thread...