Prime numbers and factoring in C and C++
Introduction to Prime Numbers
Prime Numbers are a fundamental concept in mathematics, particularly in number theory. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number is a number that cannot be formed by multiplying two smaller natural numbers.
Key Characteristics of Prime Numbers:
Significance: Prime numbers are crucial in various fields of mathematics and computer science. They play a key role in number theory, cryptography, and many algorithms that involve data security and encryption.
Examples:
Key Characteristics of Prime Numbers:
- Divisibility: A prime number ppp has exactly two distinct positive divisors: 1 and ppp.
- Examples: The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, and 19. For instance, 2 is a prime number because its only divisors are 1 and 2. Similarly, 7 is a prime number because it is only divisible by 1 and 7.
Significance: Prime numbers are crucial in various fields of mathematics and computer science. They play a key role in number theory, cryptography, and many algorithms that involve data security and encryption.
Examples:
- 2: The smallest and the only even prime number.
- 4: Not a prime number because it is divisible by 1, 2, and 4.
- 13: A prime number because its only divisors are 1 and 13.
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;
cout << "Enter the interval [a, b]: ";
cin >> a >> b;
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.
Understanding the Optimization: Checking Up to the Square Root
When determining if a number nnn is prime, we can significantly optimize the process by checking potential divisors only up to the square root of nnn. Here’s why this works:
- Divisor Pair Concept: For any divisor ddd of nnn, there is a corresponding divisor n/dn/dn/d. For example, if 666 is a divisor of 424242, then 42/6=742/6 = 742/6=7 is also a divisor. This means that divisors come in pairs, and at least one of these divisors must be less than or equal to the square root of nnn.
- Mathematical Proof:
Suppose n has a divisor d such that d > √n. Then n/d must be less than √n because d×(n/d)=n.
Therefore, if n is divisible by any number greater than √n it must also be divisible by a number smaller than or equal to √n.Thus, checking divisibility up to √n is sufficient to determine if n is prime.
Example: To check if 29 is a prime number, we only need to test divisibility by numbers up to √29 ≈5.39. Thus, we test 2, 3, and 5. Since 29 is not divisible by any of these, it is confirmed as a prime number.
#include <iostream>
using namespace std;
bool isPrime(long long n) {
if (n <= 1) return false; // Numbers less than 2 are not prime
if (n == 2 || n == 3) return true; // 2 and 3 are prime numbers
if (n % 2 == 0 || n % 3 == 0) return false; // Exclude multiples of 2 and 3
for (long long d = 5; d * d <= n; d += 6) {
if (n % d == 0 || n % (d + 2) == 0) return false; // Check divisibility
}
return true;
}
int main() {
long long a, b;
cout << "Enter the interval [a, b]: ";
cin >> a >> b;
for (long long i = a; i <= b; i++) {
if (isPrime(i)) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
using namespace std;
bool isPrime(long long n) {
if (n <= 1) return false; // Numbers less than 2 are not prime
if (n == 2 || n == 3) return true; // 2 and 3 are prime numbers
if (n % 2 == 0 || n % 3 == 0) return false; // Exclude multiples of 2 and 3
for (long long d = 5; d * d <= n; d += 6) {
if (n % d == 0 || n % (d + 2) == 0) return false; // Check divisibility
}
return true;
}
int main() {
long long a, b;
cout << "Enter the interval [a, b]: ";
cin >> a >> b;
for (long long i = a; i <= b; i++) {
if (isPrime(i)) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
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.
The 6k ± 1 optimization is based on the observation that all prime numbers greater than 3 can be expressed in the form of 6k±1. This is because:
- Divisibility by 2 and 3: Any integer can be written in one of the following forms relative to 6:
- 6k (divisible by 6)
- 6k+1 (remainder 1 when divided by 6)
- 6k+2 (divisible by 2)
- 6k+3 (divisible by 3)
- 6k+4 (divisible by 2)
- 6k+5(remainder 5 when divided by 6)
- Optimization: This reduces the number of checks needed because we can skip numbers that are obviously not primes (i.e., those divisible by 2 or 3) and focus only on numbers of the form 6k±1.
#include < iostream >
using namespace std ;
bool isPrime(long long b)
{
if(n<=1)// Numbers less than 2 are not prime
while((6*k-1)*(6*k-1)<=n)
{
return true;
return false;
if(n==2 || n==3)// 2 and 3 are prime numbers
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;// Exclude multiples of 2 and 3
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...
{
k=k+1;
}{
return false;
}k=k+1;
return true;
}
int main()
{
long long a, b ,c=0;
for(int i=a; i <= b; i++)
{
}for(int i=a; i <= b; i++)
{
if(isPrime(i))
{
}{
cout << i << " ";
c++;
if(c % 10 == 0)
}c++;
if(c % 10 == 0)
cout << endl;
Why do numbers of the form 6k ± 1 work? It may help to better understand this optimization.
Numbers that are of the form 6k ± 1 are useful for checking primality because all prime numbers greater than 3 can be expressed in this form. Numbers of the form 6k are divisible by 6, while numbers of the form 6k ± 2, 6k ± 3, and 6k ± 4 are divisible by 2 or 3. Therefore, if a number is not divisible by either 2 or 3, it must be of the form 6k ± 1.
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.
Figure 1: Delimiters of number n, display of pairs of part numbers 12 and 16
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=0; 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;
}
}
}