Prime numbers
All right, in this lesson we are going to write a program that has functions and figures out whether or not a number is prime.
A natural number is prime if it is greater than 1 and has no divisors other than 1 and itself.
Prime numbers are numbers that are not divisible by any other number besides 1
Lets take 7 for example.....
7 is divisible 1. no big deal
7 is not divisible by 2... good
7 is not divisible by 3... good
7 is not divisible by 4... good
7 is not divisible by 5... good
7 is not divisible by 6... good
Sooo 7 is a prime number
Lets take 6 for example
6 is divisible by 1. no big deal
6 is divisible by 2... so
6 is divisible by 3... so
6 is NOT a prime number
Is it important to divide a number by every number between 1 and itself?
No...
It is only important to divide the number in question up to half of its value.
the other numbers above its half way will just be a repeat of the lower half
Sooo we could take the square root of a number
for example the square root of 25 is 5
and run the code up to that point, to test if the number for divisibility.
Your task is to write a function that checks whether or not a number is prime or not.
The function: is called "isPrime";
takes one int argument (the value to check);
returns "true" if the argument is a prime number or "false" otherwise;
should be mute.
Hint: try to divide the argument by all subsequent values (starting from 2) and check the remainder – if it's 0, your number cannot be a prime;
think carefully when you should stop the process and check whether you could use the "sqrt()" function
(which you already know).
Complete the code below.
Run your code and check whether your output is the same as ours.
A natural number is prime if it is greater than 1 and has no divisors other than 1 and itself.
Prime numbers are numbers that are not divisible by any other number besides 1
Lets take 7 for example.....
7 is divisible 1. no big deal
7 is not divisible by 2... good
7 is not divisible by 3... good
7 is not divisible by 4... good
7 is not divisible by 5... good
7 is not divisible by 6... good
Sooo 7 is a prime number
Lets take 6 for example
6 is divisible by 1. no big deal
6 is divisible by 2... so
6 is divisible by 3... so
6 is NOT a prime number
Is it important to divide a number by every number between 1 and itself?
No...
It is only important to divide the number in question up to half of its value.
the other numbers above its half way will just be a repeat of the lower half
Sooo we could take the square root of a number
for example the square root of 25 is 5
and run the code up to that point, to test if the number for divisibility.
Your task is to write a function that checks whether or not a number is prime or not.
The function: is called "isPrime";
takes one int argument (the value to check);
returns "true" if the argument is a prime number or "false" otherwise;
should be mute.
Hint: try to divide the argument by all subsequent values (starting from 2) and check the remainder – if it's 0, your number cannot be a prime;
think carefully when you should stop the process and check whether you could use the "sqrt()" function
(which you already know).
Complete the code below.
Run your code and check whether your output is the same as ours.
Sample code
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num)
{
// Insert your code here
}
int main(void)
{
for(int i = 0; i <= 21; i++)
if(isPrime(i))
cout << i << " ";
cout << endl;
return 0;
}
#include <cmath>
using namespace std;
bool isPrime(int num)
{
// Insert your code here
}
int main(void)
{
for(int i = 0; i <= 21; i++)
if(isPrime(i))
cout << i << " ";
cout << endl;
return 0;
}
Sample Output
2 3 5 7 11 13 17 19