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

  • Thread starter Arman777
  • Start date
  • #1
1,785
139
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
 
Last edited:

Answers and Replies

  • #2
BvU
Science Advisor
Homework Helper
2019 Award
13,410
3,190
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 ... :rolleyes: 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 < 1012 . Do you think you can shorten it somewhat by introducing a loop in an appropriate line ?
 
  • #3
1,785
139
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.
 
Last edited:
  • #4
33,712
5,411
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.

Arman777 said:
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##.
 
  • Like
Likes QuantumQuest
  • #5
BvU
Science Advisor
Homework Helper
2019 Award
13,410
3,190
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.
 
  • #6
1,785
139
"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
 
Last edited:
  • #7
33,712
5,411
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:
Mark44 said:
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.
 
Last edited:
  • #8
1,785
139
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.
 
  • #9
33,712
5,411
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.
Code:
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.
 
  • #10
1,785
139
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.
Code:
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.
 
  • #11
33,712
5,411
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.
 
  • #12
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
@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.
 
  • #13
1,785
139
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".
 
  • #14
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,892
3,637
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.
 
Last edited:
  • Like
Likes Arman777
  • #15
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
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?
 
  • #16
1,785
139
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 thats all.
 
  • #17
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,892
3,637
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.
 
  • #18
1,785
139
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 cant do it myself..I should just look for square root N thing then.
 
  • #19
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,892
3,637
Hmm..its how it writes on the slide..I guess I cant 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
Code:
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
 
Last edited:
  • Like
Likes BvU
  • #20
33,712
5,411
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.
 
  • Like
Likes BvU
  • #21
BvU
Science Advisor
Homework Helper
2019 Award
13,410
3,190
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.
 
  • Like
Likes Arman777
  • #23
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,892
3,637
Cause I said M=2 ?
The problem is on step 9.
Code:
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.
 
  • #24
1,785
139
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
 
  • #25
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
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.
 

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
980
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
8
Views
775
Top