Table of Contents
- 1. Determine the prime number
-
- Idea analysis
- Code
- 2. Decomposition prime factor
-
- Idea analysis
- Typical topics
- Code
- Three, prime number sieve
-
- classic topic
- Idea analysis
-
- 1. Naive sieve method
- 2. Elsieve sieve method
- 3. Euler sieve method
1. Determine the prime number
Thinking Analysis
Since the factors of each composite number appear in pairs, that is, if
d
d
d is
no
no
factor of n, then
no
d
\frac{n}{d}
dn? also
no
no
factor of n, so from
1
1
1 to
no
no
The enumeration of n can be reduced to
1
1
1 to
no
\sqrt{n}
no
d
≤
no
d
d \leq \frac{n}{d}
d≤dn?, so that
d
≤
no
d \leq \sqrt{n}
d≤n
Code Implementation
bool is_prime(int n)
{<!-- -->
if (n < 2) return false;
for (int i = 2; i <= n / i; + + i)
{<!-- -->
if (n % i == 0) return false;
}
return true;
}
Time complexity:
o
(
no
)
O(\sqrt{n})
O(n
2. Decompose prime factor
Thinking Analysis
Every composite number is obtained by multiplying prime numbers together. Composite numbers can be written as the product of prime factors, which is a fundamental proposition in number theory.
For example:
12 = 2 * 2 * 3
18 = 2 * 3 * 3
24 = 2 * 2 * 2 * 3
① For any composite number
no
no
n, in its prime factorization, has at most one prime factor greater than
no
\sqrt{n}
no
② At the same time, it can also be launched, for any composite number
no
no
n, in its prime factorization, has at least one prime factor less than or equal to
no
\sqrt{n}
no
Typical Topics
Description of topic:
given
no
no
n positive integers
a
i
a_i
ai?, decompose each number into prime factors, and output the base and exponent of each prime factor in ascending order of prime factors.
Enter format:
The first row contains integers
no
no
n.
next
no
no
n lines, each containing a positive integer
a
i
a_i
ai?.
Output format:
for every positive integer
a
i
a_i
ai?, after outputting its decomposed prime factors in order from small to large, the base and exponent of each prime factor, each base and exponent occupies one line.
After outputting all the prime factors of each positive integer, output a blank line.
Data range:
1
≤
no
≤
100
,
2
≤
a
i
≤
2
?
1
0
9
1≤n≤100, 2≤a_i≤2*10^9
1≤n≤100, 2≤ai?≤2?109
Sample input:
2 6 8
Sample output:
2 1 3 1 twenty three
Code Implementation
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
void divide(int x)
{<!-- -->
for (int i = 2; i <= x / i; + + i) // traverse all prime factors less than or equal to sqrt(n)
{<!-- -->
if (x % i == 0)
{<!-- -->
int cnt = 0;
while (x % i == 0)
{<!-- -->
cnt + + ;
x /= i;
}
cout << i << ' ' << cnt << endl;
}
}
// Output the prime factor greater than sqrt(n) or the prime number itself
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
int main()
{<!-- -->
int n;
cin >> n;
while (n--)
{<!-- -->
int x;
cin >> x;
divide(x);
}
return 0;
}
Time complexity: in
o
(
log
?
no
)
O(\log n)
O(logn) with
o
(
no
)
O(\sqrt n)
O(n
no
no
n is
2
2
2 times, the time complexity will become
o
(
log
?
no
)
O(\log n)
O(logn).
3. Prime number sieve
Classic topic
Description of topic:
Given a positive integer
no
no
n, please find out
1
~
no
1～n
The number of prime numbers from 1 to n.
Enter format:
one line, containing integers
no
no
n.
Output format:
A total of one line, containing an integer, said
1
~
no
1～n
The number of prime numbers from 1 to n.
Data range:
1
≤
no
≤
1
0
6
1≤n≤10^6
1≤n≤106
Sample input:
8
Sample output:
4
Thinking Analysis
By screening out the multiples of prime numbers, the remaining ones are all prime numbers.
After sieving
P
P
P with
2
2
2 ~ (
P
?
1
P-1
There is no multiple relationship between P?1), that is,
P
P
P massless factor in
2
2
2 ~ (
P
?
1
P-1
P?1) between.
1. Simple sieve method
Get all the prime numbers in the range by sieving out the multiples of all numbers from 2 to n
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N];
void get_prime(int n)
{<!-- -->
for (int i = 2; i <= n; + + i)
{<!-- -->
if (!st[i])
{<!-- -->
prime[cnt + + ] = i;
}
for (int j = 2 * i; j <= n; j + = i) st[j] = true; // mark all multiples of 2~n
}
}
int main()
{<!-- -->
int n;
cin >> n;
get_prime(n);
cout << cnt << endl;
return 0;
}
time complexity:
o
(
no
log
?
no
)
O(n \log n)
O(nlogn)
no
2
+
no
3
+
no
4
+
.
.
.
+
+
no
no
=
no
(
1
2
+
1
3
+
1
4
+
.
.
.
+
1
no
)
\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + … + + \frac{n}{n} = n(\frac{1}{2 } + \frac{1}{3} + \frac{1}{4} + … + \frac{1}{n})
2n? + 3n? + 4n? + … + + nn?=n(21? + 31? + 41? + … + n1?)
Harmony levels:
lim
?
no
→
∞
(
1
2
+
1
3
+
1
4
+
.
.
.
+
1
no
)
=
ln
?
no
+
c
\lim_{n \to \infty} (\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + … + \frac{1}{n}) = \ln n + c
limn→∞?(21? + 31? + 41? + … + n1?)=lnn + c (Euler’s constant
c
=
0.577
c = 0.577
c=0.577)
Therefore, the time complexity can be obtained as
o
(
no
log
?
no
)
O(n \log n)
O(nlogn)
2. Elsieve sieve
Optimized the simple sieve method, only the multiples of 2~n prime numbers are screened out to get all the prime numbers within the range
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N];
void get_prime(int n)
{<!-- -->
for (int i = 2; i <= n; + + i)
{<!-- -->
if (st[i]) continue;
prime[cnt + + ] = i;
for (int j = 2 * i; j <= n; j + = i) st[j] = true; // Mark the multiples of all prime numbers from 2 to n
}
}
int main()
{<!-- -->
int n;
cin >> n;
get_prime(n);
cout << cnt << endl;
return 0;
}
The time complexity is
o
(
no
log
?
log
?
no
)
O(n \log \log n)
O(nloglogn)
The prime number theorem: in
1
1
1 to
no
no
The number of prime numbers between n is approximately equal to
no
ln
?
no
\frac{n}{\ln n}
lnnn?
3. Euler Sieve
Core idea: On the basis of the Esperanto sieve method, let each composite number be screened only once by its smallest prime factor to achieve no repeated purpose.
step:
- from
i
=
2
i = 2
i=2 starts, if
i
i
i has not been screened out, then the
i
i
i is added to the list of prime numbers.
- iterate over the current list of prime numbers
p
r
i
m
e
[
]
prime[]
prime[], filter out
i
?
p
r
i
m
e
[
j
]
i ? prime[j]
i?prime[j].
(ensurep
r
i
m
e
[
j
]
?
i
prime[j]?i
prime[j]?i cannot cross the boundary, because the result is meaningless if it crosses the boundary. Right now
i
?
p
r
i
m
e
[
j
]
≤
no
i ? prime[j] \leq n
i?prime[j]≤n)
- When traversing to a prime number that can divide i
p
r
i
m
e
[
j
]
prime[j]
prime[j], filter out
i
?
p
r
i
m
e
[
j
]
i ? prime[j]
i?prime[j], stop traversing the list of prime numbers.
- repeat
2
,
3
,
4
2,3,4
2,3,4, until all do not exceed
no
no
The integers of n have been traversed through the elements in the list of prime numbers, that is, the requested value does not exceed
no
no
All prime numbers of n.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int cnt, prime[N];
bool st[N];
void get_prime(int n)
{<!-- -->
for (int i = 2; i <= n; + + i)
{<!-- -->
if (!st[i]) prime[cnt + + ] = i;
for (int j = 0; prime[j] <= n / i; j++ )
{<!-- -->
st[prime[j] * i] = true;
if (i % prime[j] == 0) break; // filter only once by its smallest prime factor
}
}
}
int main()
{<!-- -->
int n;
cin >> n;
get_prime(n);
cout << cnt << endl;
return 0;
}
like
no
< 1 0 6 n<10^6 n<106, the Euler sieve and the Escher sieve take about the same time; but if no >
1
0
7
n>10^7
n>107, the Euler sieve will be about twice as fast as the Esperanto sieve.