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

  • Thread starter Arman777
  • Start date
  • #26
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,920
3,653
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:
  • Like
Likes PeroK and Arman777
  • #27
1,785
139
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 ?

Sad that 4 didnt work out..okay I can add
 
  • #28
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,920
3,653
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
Sad that 4 didnt work out..okay I can add
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.
 
  • #29
1,957
252
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. :wink:
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.
 
  • #30
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,920
3,653
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.
 
  • Like
Likes Arman777
  • #31
1,785
139
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...
 
  • #32
1,957
252
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.
 
  • #33
1,785
139
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..
 
  • #34
1,785
139
I have also questions for my other flowchart..I ll open another thread...
 

Related Threads on Making an Algorithm to Check Whether a Number is a Prime Number

Replies
1
Views
1K
  • Last Post
Replies
8
Views
4K
  • Last Post
2
Replies
39
Views
2K
Replies
0
Views
3K
  • Last Post
Replies
11
Views
4K
Replies
14
Views
2K
Replies
1
Views
983
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
8
Views
777
Top