Prime numbers and factoring in C and C++
For some natural number we say that it is simple, if it is only divisible by 1 and with itself. Let's look at the following problem:
Determine all prime numbers in the interval from a to b.
This problem often arises in solving some more complex tasks.
One of the possible solution algorithms:
After the numbers a (start of interval) and b (end of interval) are entered, it is necessary to go through all the numbers in this interval using a loop. For each of these numbers, it is checked whether it is a prime number and if it is, it should be printed on the screen.
Checking if a number is prime (method):
If the number is 1 or 2, the numbers are prime. If they are not prime numbers, introduce a bool variable that is initially set to true. This means that we assume that the number will be prime. Through the cycle, we change the divisor starting from two and continue until we find the one with which the tested number will be divisible. When we get there, we stop the cycle. If the last divisor is smaller than the tested number, then it means that the number is not prime, because it is divisible by a number other than unity and itself (definition of a prime number).
In this case, the bool variable should be changed to false.
So the return value of the method will be true if the number is prime or false if it is not.
This problem often arises in solving some more complex tasks.
One of the possible solution algorithms:
After the numbers a (start of interval) and b (end of interval) are entered, it is necessary to go through all the numbers in this interval using a loop. For each of these numbers, it is checked whether it is a prime number and if it is, it should be printed on the screen.
Checking if a number is prime (method):
If the number is 1 or 2, the numbers are prime. If they are not prime numbers, introduce a bool variable that is initially set to true. This means that we assume that the number will be prime. Through the cycle, we change the divisor starting from two and continue until we find the one with which the tested number will be divisible. When we get there, we stop the cycle. If the last divisor is smaller than the tested number, then it means that the number is not prime, because it is divisible by a number other than unity and itself (definition of a prime number).
In this case, the bool variable should be changed to false.
So the return value of the method will be true if the number is prime or false if it is not.
int main()
{
long long a,b,c=0;
cin >> a >> b;
for(int i=a;i<=b;i++){
if(isProst(i)){
cout << i << " ";
c++;
if(c%10==0)cout << endl;
}
}
return 0;
}
{
long long a,b,c=0;
cin >> a >> b;
for(int i=a;i<=b;i++){
if(isProst(i)){
cout << i << " ";
c++;
if(c%10==0)cout << endl;
}
}
return 0;
}
#include < iostream >
using namespace std ;
bool isPrime(long long b){
if(b==1 || b==2)
return true;// 1 i 2 are prime numbers
bool r=true;
long d=2;
/* Search for a number that is a divisor of number b in segment 2 through b*/
while(b % d != 0 )// The condition of the loop is that b is not divisible by d
{
d++;
}
if(d < b)
r=false;
return r;
}
int main(){
long long a, b ,c=0;
for(int i=a; i <= b; i++)
{
if(isPrime(i))
{
cout << i << " ";
c++;
if(c % 10 == 0)
cout << endl;
}
}
}
This algorithm is too slow for large numbers that are greather than (>) 109.
The largest number of iterations is n, and may be smaller if we first find the number that is partitioned with the number tested, and that it is not 1 or n. In this case, the end of the loop in which the check is performed ends before.
There is a way to determine whether the number is prime, which is explained further in the text.
Reducing the number of iterations from n to √n
If we analyze a little better the dividers of a number, we can notice that if d is a part of some number n and n / d will also be a part of that same number. For example. Number 6 is a part of number 42, but also number 7 = 42/6. It can be further noted that at least one of these two parties must be less than or equal to √n
.
In the case that both partitions are equal, the number n is their total square, and the value of both parties is exactly equal to √
n
.
On the basis of this we can conclude that it is necessary to check the number of n for at most n = 1/2.#include < iostream >
using namespace std ;
bool isPrime(long long n)
{
if(n==1)
return false;
long long d=2;
while(d*d<=n){
if(n % d == 0)
{
return false;
}
d=d+1;
}
return true;
}
int main()
{
long long a, b ,c=0;
for(int i=a; i <= b; i++)
{
if(isPrime(i))
{
cout << i << " ";
c++;
if(c % 10 == 0)
cout << endl;
}
}
}
Let's look at a function that checks if the number n is empty. First check whether n is equal to 1. If it is, it exits from function and returns false. Other potential partitions to be checked are 2 until they encounter a number that is divisible by n or, in the worst case, to n ^ 1/2, including n ^ 1/2. If through time, a number that is divisible is output from a function with a return value equal to false, because in this case the number is not prime.
The algorithm examines whether the number is prime using a 6k + 1 theorem
This theorem says that each prime number is greater than 3 forms or 6k + 1 or 6k-1. This can speed up the previous algorithm by checking whether the number is prime is done only for the numbers 6k + 1 and 6k-1.
#include < iostream >
using namespace std ;
bool isPrime(long long b)
{
if(n==1)
return false;
if(n==2 || n==3)
return true;
long long k=1;
while((6*k-1)*(6*k-1)<=n)
{
if(n % (6*k-1) == 0 || n % (6*k+1) == 0)//Examines only forms: 6k+1 i 6k-1, k=1,2,3...
{
return false;
}
k=k+1;
}
return true;
}
int main()
{
long long a, b ,c=0;
for(int i=a; i <= b; i++)
{
if(isPrime(i))
{
cout << i << " ";
c++;
if(c % 10 == 0)
cout << endl;
}
}
}
Determining all divisors of a number
Determining any partition of a number can also be solved by examining the order of all numbers, which are smaller than n. This is as we said in the previous text, correct only for numbers up to a maximum of 10 ^ 9. Determination of all parties should be different from factorization. In the first case, we determine the numbers with which a number is n divided and we write the dividers every one time. For n = 12 it would be:
Delimiters number 12: 1,2,3,4,6,12
Factoring would be to write the product of the dealers who would give the number n. For n = 12, factorization would mean:
12 = 1 * 2 * 2 * 3
In determining the sender, as well as in determining the free numbers, the conclusion is that it is sufficient to examine the numbers up to a value of n ^ 1/2. Each particle d has its pair n / d. This is shown in Figure 1. For example, the divisors of numbers 12: 1 and 12, 2 and 6, 3 and 4. The divisors of number 16 are: 1 and 16, 2 and 8, 4 and 4. So here we see that 4 is in pairs with yourself and that 4 = 16 ^ 1/2.
Delimiters number 12: 1,2,3,4,6,12
Factoring would be to write the product of the dealers who would give the number n. For n = 12, factorization would mean:
12 = 1 * 2 * 2 * 3
In determining the sender, as well as in determining the free numbers, the conclusion is that it is sufficient to examine the numbers up to a value of n ^ 1/2. Each particle d has its pair n / d. This is shown in Figure 1. For example, the divisors of numbers 12: 1 and 12, 2 and 6, 3 and 4. The divisors of number 16 are: 1 and 16, 2 and 8, 4 and 4. So here we see that 4 is in pairs with yourself and that 4 = 16 ^ 1/2.
A program that determines all the divisors of the number n:
#include < iostream >
#define DIM 100
using namespace std ;
int d[DIM];
long long allDividers(long long n)
{
long long m=0;
long long i=1;
while(i*i < n)
{
if(n % i == 0)
{
d[m+1]=i;
d[m+2]=n/i;
m=m+2;
}
i=i+1;
}
if(i*i == n)
{
m=m+1;
d[m]=i;
}
return m;
}
int main()
{
long long N,m;
cin >> N;
m=allDividers(N);
for(int i=1;i<=m;i++){
cout << d[i] << endl;
}
}
Factoring of the number N
Factoring of a certain number is its disassembly into free factors, i.e. Some N write in the form:
Unlike the determination of all the parties where the division of all numbers from 2 to n ^ 1/2 is examined, and if the potential divisor is divisible, it switches to the next divisor, which is done in the part of the code that was previously shown:
while(i*i < n)
{
if(n%i==0)
{
d[m+1]=i;
d[m+2]=n/i;
m=m+2;
}
i=i+1;
}
if(i*i==n)
{
m=m+1;
d[m]=i;
}
{
if(n%i==0)
{
d[m+1]=i;
d[m+2]=n/i;
m=m+2;
}
i=i+1;
}
if(i*i==n)
{
m=m+1;
d[m]=i;
}
when factorizing, it is necessary to repeat the sharing process with the same sender as long as the remainder of the division of the number n is divisible to the potential sender d. The solution to the algorithm could be:
#include < iostream >
#define DIM 100
using namespace std ;
int a[DIM];
int p[DIM];
int faktoring(int n)
{
int k=0;
int d=2;
while (d*d<=n) {
if(n % d == 0){
k=k+1;
a[k]=0;//Exhibitor who is remembered in a series
p[k]=d;
while(n % d==0){
n=n/d;
a[k]=a[k]+1;
}
}
d=d+1;
}
if(n>1){
k=k+1;
p[k]=n;
a[k]=1;
}
return k;
}
int main()
{
int N,k;
cin << N;
k=faktoring(N);
for(int i=1; i<=k; i++)
{
for(int j=1; j<=a[i]; j++) {
cout << p[i] << endl;
}
}
}