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

[Arman777]

1. The problem statement, all variables, and given/known data
Create algorithm steps that for a given number (N) is prime or not

Homework Equations

3. The Attempt at a Solution
I am trying to create an algorithm but I am stuck at some place.
Here is my trying.
1-Input a non-negative integer N
2-If N=2 go step n
3-If N>2 go to step 4
4-Calculate N\2
5-If Remaining number of N\2=0 go step m, otherwise, go 6
6-Calculate N\3
7- If remaining number N\3=0 go step m, otherwise go step 8-
8-Calculate N\4
9- If remaining number 0 go step m, otherwise go step 10.
10-Calculate N\5
11-If remaining number 0 go to step m, otherwise, go to step

Now step "m" will represent false (not a prime number) and step "n" will represent true (its a prime number). I want to stop this when N=N but I am not sure how to write it..Or this method is valid?
I can do this until N\N and If it comes until N (The last step), then I ll say its prime.

Thanks

 

[BvU]

Not sure what your question is? If you want to test your algorithm, just do it on a piece of paper for, e.g. the numbers 28 and 29.

And it looks as if the copy/paste work didn't go faultless ... perhaps you should also trry to read carefuly what you posted !

However,
This is a very lengthy algorithm if you want to use it for all numbers N < 10¹² . Do you think you can shorten it somewhat by introducing a loop in an appropriate line ?

 

[Arman777]

ot sure what your question is? If you want to test your alogorithm, just do it on a piece of paper for, e.g. the numbers 28 and 29.

I guess it works yes

This is a very lengthy algorithm if you want to use it for all numbers N < 1012 . Do you think you can shorten it somewhat by introducing a loop in an appropriate line ?

yes exactly..But I am not sure how to do it.

 

[Mark44]

1. The problem statement, all variables, and given/known data
Create algorithm steps that for a given number (N) is prime or not

Homework Equations

3. The Attempt at a Solution
I am trying to create an algorithm but I am stuck at some place.
Here is my trying.
1-Input a non-negative integer N
2-If N=2 go step n
3-If N>2 go to step 4
4-Calculate N\2
5-If Remaining number of N\2=0 go step m, otherwise, go 6
6-Calculate N\4
7- If remaining number N\3=0 go step m, otherwise go step 8-
8-Calculate N\5
9- If remaining number 0 go step m, otherwise go step 10.
10-Calculate N\6
11-If remaining number 0 go to step m, otherwise, go to step

Some comments:
"3-If N>2 go to step 4" -- This makes no sense. If n > 2, we go to step 4. If n <= 4, we go to step 4, as well.
"2-If N=2 go step n" -- You have to identify which step you're talking about. Same comment for steps 5, 7, 9, and 11.
"4-Calculate N\2" -- use / for division, not \

The major problem with this algorithm is that it isn't useful. You are checking lots of things that don't need to be checked. If a number isn't divisible by 2, then it definitely won't be divisible by 4, 6, 8, or any other even number.

Now step "m" will represent false (not a prime number) and step "n" will represent true (its a prime number). I want to stop this when N=N but I am not sure how to write it..Or this method is valid?
I can do this until N\N and If it comes until N (The last step), then I ll say its prime.

A simple algorithm is the Sieve of Eratosthenes. If your input number is N, then you need to check only the prime divisors of N up to $\sqrt N$. That is, you need to check only 2, 3, 5, 7, 11, 13, 17, 19, ..., $\sqrt N$.

 

[BvU]

yes exactly..But I am not sure how to do it.

Well, what are you going to do about it (except asking someone else to do the work for you, from which you yourself don't learn very much) ?

You don't have any relevant equations listed, but you could write down a few thoughts there, like:

• I only have to test odd numbers (after N = 2)
• I don't have to test further than $\sqrt{}$ N
• ...

[edit]I see Mark gave you a few ideas too. I don't like the idea that you need a list of primes to find out if a number is prime, but I agree it is a way.

 

[Arman777]

"3-If N>2 go to step 4" -- This makes no sense. If n > 2, we go to step 4. If n <= 4, we go to step 4, as well.

Why? Well, I forget to add for N=1 but for N=2 it will go the prime number answer which is step "n" as I said. For N=3 I can also do the same thing actually.

"n" will represent true (its a prime number).

2-If N=2 go step n" -- You have to identify which step you're talking about. Same comment for steps 5, 7, 9, and 11.

I'll If I can finish the algorithm. For now, I can't define a proper number of those steps so I used "n" or "m" to represent it.

Well, what are you going to do about it (except asking someone else to do the work for you, from which you yourself don't learn very much)?

Yes, I want to do it myself. I thought to create another number M and then say like divide N/M then M+1 and repeat that M+1 constantly until M+1=N

So here last form.

input: N
Output: True If N is prime, False If N is not a prime

1-Input a non-negative integer N
3-If N=1 go step 12
3-If N=2 go step 11
4-If N=3 go step 11
5-If N>3 go to step 6
6-Let M=2
7=M=M+1
8-Calculate N\M
9-If remaining number of N\M is 0 go to step 12, otherwise, go to step 7
10-If N/M=1 go to step 11
11-N is a prime number
12-N is not a prime number

 

[Mark44]

3-If N>2 go to step 4
4-Calculate N\2

Why? Well, I forget to add for N=1 but for N=2 it will go the prime number answer which is step "n" as I said. For N=3 I can also do the same thing actually.

But that's not what you wrote. If N = 3, you have N > 2, so you go to step 4. If you have steps for N = 1 or N = 2, you didn't show them. In an algorithm (or code) you should never "goto" the next step, since that's what would happen anyway.

Also, you didn't notice, or at least comment on my earlier remark:

A simple algorithm is the Sieve of Eratosthenes. If your input number is N, then you need to check only the prime divisors of N up to $\sqrt N$. That is, you need to check only 2, 3, 5, 7, 11, 13, 17, 19, ..., $\sqrt N$.

Your algorithm, as it currently is, probably won't get you many points from your instructor. As already noted it's not a good idea to check for primes using a list of primes.

 

[Arman777]

Well, we will not going to write an algorithm actually but we will just to make a flowchart. So I wrote it like that

In an algorithm (or code) you should never "goto" the next step since that's what would happen anyway.

I see your point. But also I should note them If they are not going to next step.

Your algorithm, as it currently is, probably won't get you many points from your instructor.

Why? Something wrong with it?

Also, you didn't notice, or at least comment on my earlier remark:

I wanted to be original and wanted to think myself. I know that If I can search online I can find many algorithms for it.

 

[Mark44]

In an algorithm (or code) you should never "goto" the next step, since that's what would happen anyway.

I see your point. But also I should note them If they are not going to next step.

In my earlier comment it wasn't clear that you were doing a flow chart, so my comments assumed you were writing an algorithm.

I don't think you're getting my point.
Here's an example, in C, of what I'm talking about.

x = 1
if (x == 1) goto A;
A: x = x + 1;

If x happens to be equal to 1, control is transferred to the line whose label is A.
If x is any other value, control is transferre to the line whose label is A.

In other words, the line whose lable is A gets executed regardless of the value of x.

 

[Arman777]

In my earlier comment it wasn't clear that you were doing a flow chart, so my comments assumed you were writing an algorithm.

I don't think you're getting my point.
Here's an example, in C, of what I'm talking about.

x = 1
if (x == 1) goto A;
A: x = x + 1;

If x happens to be equal to 1, control is transferred to the line whose label is A.
If x is any other value, control is transferre to the line whose label is A.

In other words, the line whose lable is A gets executed regardless of the value of x.

I see your point, I ll think about it.

 

[Mark44]

1-Input a non-negative integer N
3-If N=1 go step 12
3-If N=2 go step 11
4-If N=3 go step 11
5-If N>3 go to step 6
6-Let M=2
7=M=M+1
8-Calculate N\M
9-If remaining number of N\M is 0 go to step 12, otherwise, go to step 7
10-If N/M=1 go to step 11
11-N is a prime number
12-N is not a prime number

This is more reasonable, but it does calculations that are unnecessary. For example, if N = 7 you calculate N/3, N/4, N/5, N/6, and finally, N/7. You don't need to got through every possible divisor in the set {3, ..., N}. As BvU and I both said, you only need to check up to at most $\sqrt N$. In this case you need to check only up to 2.

Note that when you write division, use /, not \. No programming language uses \ for division.

 

[QuantumQuest]

@Arman777

One thing I don't understand at all from the outset is why you're using "goto" steps. It has long been abandoned in programming because it produces "spaghetti" code. So, there is no reason to use it in pseudocode too. Instead you must introduce conditional and repetition structures so your program will execute in a more reasonable manner.

Also, you have to choose the algorithm that will do the real job first even if you want to come up with your own idea - although I don't recommend it unless you have to do it this way. So, I think it's best to follow what Mark44 suggested (Sieve of Eratosthenes) as a simple approach and there are other approaches too.
If you want to create an algorithm yourself, the simplest one i.e. brute force approach is obviously not efficient as n grows large. So, you can optimize it using the fact that a larger factor of n must be a multiple of a smaller factor and so you can use $\sqrt{n}$ instead of n. Also, this can be further improved if you find a pattern (form) of all primes - I leave it to you to find out how.

 

[Arman777]

Note that when you write division, use /, not \. No programming language uses \ for the division.

Yes, thanks. I don't know why I keep doing that.

This is more reasonable, but it does calculations that are unnecessary. For example, if N = 7 you calculate N/3, N/4, N/5, N/6, and finally, N/7. You don't need to get through every possible divisor in the set {3, ..., N}.

f x happens to be equal to 1, control is transferred to the line whose label is A.
If x is any other value, control is transferred to the line whose label is A.

In other words, the line whose label is A gets executed regardless of the value of x.

I didn't understand I thought it was wrong?

As BvU and I both said, you only need to check up to at most √NN\sqrt N. In this case you need to check only up to 2.

Note that when you write division, use /, not \. No programming language uses \ for the division.

Okay, well I 'll think about it.

One thing I don't understand at all from the outset is why you're using "goto" steps

Well, I am taking computer science course first time and this is the 2 and week of the course. I saw go to in one of my teacher's example so that's why I wrote: "go to".

 

[jbriggs444]

9-If remaining number of N\M is 0 go to step 12, otherwise, go to step 7
10-If N/M=1 go to step 11

Step 10 is dead code and will never be executed.

Edit: Accordingly, 2 and 3 are the only prime numbers. Every other number is a "composite" equal to the product of itself and 1.

 

[QuantumQuest]

Well, I am taking computer science course first time and this is the 2 and week of the course. I saw go to in one of my teacher's example so that's why I wrote: "go to".

In other words are you taught to write pseudocode this way? I ask because it seems weird to me. Anyway are you asked to implement it in some programming language other than the old Basic?

 

[Arman777]

n other words are you taught to write pseudocode this way?

No not really...we have seen just one example
Input a nonnegative integer – N
2 Let fact=1
3 If N>1 go to step 5, otherwise go to step 7
4 fact=fact × N
5 N=N-1
6 Go to step 3
7 Output fact

Anyway are you asked to implement it in some programming language other than the old Basic?

Well we have just to write step by step description for how to find the prime number thing then make a flowchart that's all.

 

[jbriggs444]

3 If N>1 go to step 5, otherwise go to step 7
4 fact=fact × N

In this code, step 4 is dead. This is not a correct factorial algorithm.

Edit: Apparently the correct terminology is "unreachable", not "dead". Dead code is code whose results are never used. Unreachable code is code which can never even be executed.

 

[Arman777]

In this code, step 4 is dead. This is not a correct factorial algorithm.

Hmm..its how it writes on the slide..I guess I can't do it myself..I should just look for square root N thing then.

 

[jbriggs444]

Hmm..its how it writes on the slide..I guess I can't do it myself..I should just look for square root N thing then.

Then the slide is utterly wrong.

Let's code up something that might actually work

1 Input a nonnegative integer – N
2 Let fact=1
3 If N <= 1 go to step 7
4 fact=fact × N
5 N=N-1
6 Go to step 3
7 Output fact

An important skill is to be able to step through a piece of code one line at a time taking the actions indicated for each step.

Try it for an input of 0
Try it for an input of 1
Try it for an input of 2
Try it for an input of 3

 

[Mark44]

One thing I don't understand at all from the outset is why you're using "goto" steps. It has long been abandoned in programming because it produces "spaghetti" code.

Not completely abandoned. I've seen it in Windows source code, with the rationale that using "goto" makes the handling of very unusual exceptions much simpler, eliminating or minimizing the need to unwind the call stack for deeply embedded functions. I can't say for sure, but I would expect that there are goto's in Linux code, as well.

From "Code Complete," by Steve McConnell, p. 348, in a section titled "The Argument for gotos":

The goto is useful in a routine that allocates resources, performs operations on those resources, and then deallocates the resources. With a goto, you can clean up in one section of code. The goto reduces the likelihood of your forgetting to deallocate the resources in each place you detect an error.

In some cases, the goto can result in faster and smaller code. Knuth's 1974 article cited a few cases in which the goto produced a legitimate gain.

Good programming doesn't mean eliminating gotos. Methodical decomposition, refinement, and selection of control structures automatically lead to goto-free programs in most cases. Achieving gotoless code is not the aim, but the outcome, and putting focus on avoiding gotos isn't helpful.

Two decades' worth of research with gotos has failed to demonstrate their harmfulness. In a survey of the literature, B.A. Sheil concluded that unrealitic test conditions, poor data analysis, and inconclusive results failed to support the claim of Shneiderman and others that the number of bugs in code was proportional to the number of gotos (1981)...

In fairness, McConnell also has a section titled "The Argument Against gotos".

Regarding the algorithm/flow chart of this thread, a goto between steps is reasonable, but would normally be presented in a flow chart, (a drawing), not a list of steps. If the OP hasn't been introduced to decision structures such as if... then or repetition structures such as for loops or while loops, he's pretty much stuck with using gotos.

 

[BvU]

Well, I am taking computer science course first time and this is the 2nd week of the course

So for you it's important to learn how to set up an algorithm, either in the form of a flowchart or in pseudocode.
Let's not digress in a goto/nogoto discussion.

 

[Arman777]

Step 10 is dead code and will never be executed.

Cause I said M=2 ?

 

[jbriggs444]

Cause I said M=2 ?

The problem is on step 9.

9-If remaining number of N\M is 0 go to step 12, otherwise, go to step 7

The only possible outcomes of step 9 are to go to steps 7 or 12. There is no possibility where execution proceeds to step 10.

 

[Arman777]

I guess I solved

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

 

[QuantumQuest]

Not completely abandoned. I've seen it in Windows source code, with the rationale that using "goto" makes the handling of very unusual exceptions much simpler, eliminating or minimizing the need to unwind the call stack for deeply embedded functions. I can't say for sure, but I would expect that there are goto's in Linux code, as well.

From "Code Complete," by Steve McConnell, p. 348, in a section titled "The Argument for gotos":
In fairness, McConnell also has a section titled "The Argument Against gotos".

Yes, you're right in that they are not completely abandoned. I was talking about most high level programming languages (not in machine level) and software constructs. And there are very good arguments in my opinion that still hold true against the use of goto statements. Some very good arguments had been made early on by E.W..Dijkstra influenced by Peter Landin and Christopher Strachey. Some arguments about the restriction of goto statements had been made earlier by C.A.R. Hoare and Jacopini seems to have proved the logical superfluousness of the goto statement.

Regarding the algorithm/flow chart of this thread, a goto between steps is reasonable, but would normally be presented in a flow chart, (a drawing), not a list of steps. If the OP hasn't been introduced to decision structures such as if... then or repetition structures such as for loops or while loops, he's pretty much stuck with using gotos.

Yes, it seemed a little weird to me to write pseudocode with "goto"'s but if it is like presenting in some way a flowchart, then yes. I think that the OP will learn about how to write pseudocode properly later on.

 

[jbriggs444]

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]

#!/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

 

[Arman777]

Try that code using 4 as an input.

Edit: I actually turned this into machine-readable code. [Somewhat cringe-worthy, but it runs]

#!/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

 

[jbriggs444]

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.

 

[willem2]

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.

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]

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]

I couldn't 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...

 

[willem2]

I couldn't 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 which values of m the trial division is done. if you have

for m in range (2, n/2):

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.

 

[Arman777]

If you really have to make flowcharts, i would recommend to make and test a correct program first,

I don't 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..

 

[Arman777]

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