【 Problem description 】
Xiao Lan likes scientific research very much , He recently made an experiment and got a batch of experimental data , That's twomillion positive integers . If as expected , All the experimental data x All should be satisfied 10⁷ ≤ x ≤ 10⁸. But there will be some errors when doing experiments , It will lead to some unexpected data , This error data y The range is 10³≤ y ≤ 10¹² . Because Xiao Lan is very reliable in doing experiments , So of all his experimental data 99.99% All the above are in line with expectations . All the experimental data of Xiaolan are in primes.txt in , Now he wants to count how many of the twomillion positive integers are prime numbers , Can you tell him ？
【 Answer submission 】
This is a question to fill in the blanks , You just need to work out the results and submit them . The result of this question is an integer , Only fill in the whole number when submitting the answer , Fill in the extra content will not be able to score .
【 Thought analysis 】
At the end of the question, I figured out how to do it ,,, Didn't hand it in , Lost
This question has 200w Number , Direct violence is definitely not enough . I took a detour at the beginning , Multithreading , Primes are used to judge and optimize . Finally, I found that I thought too much , Before the end of the game 1 Minutes before the number explodes , There is no time to write prime tests for large numbers .. Ideas as follows ：
First look at the data , in 1、3、5、7 ending . Greater than 1000 And it ends with 5 Number of numbers , It must be 5 to be divisible by , So we use the editor regular to replace all the 5 Ending number , At this point, about 150w More than one number ：
\d+?5
Use Ehrlich screening , get 10^8 All prime numbers within , Note here , The use of Ehrlich screening needs to be optimized , Otherwise, it is also a big runner . In my previous blog, I also wrote the optimization method of directly judging prime numbers , except 2、3, All prime numbers lie in 6n about . Therefore, the step length of Ehrlich screening method can be directly pulled to 6, In this way, the speed can be further improved , Then the main factors that affect the speed of Ehrlich screening are 2、3、5, It takes several cycles to sift out the resultant number behind , Therefore, the preprocessing will directly generate the list 2、3、5 Multiple return of 0. Theoretically, the more prime multiples directly return to zero , The faster primes are generated .
Count prime Python Ehrlich screening _AYO_YO The blog of -CSDN Blog
Judge the prime number Python Java C++_AYO_YO The blog of -CSDN Blog
def getprimes(n):
ls = [i if i % 2 != 0 and i % 3 != 0 and i % 5 != 0 else 0 for i in range(n + 1)]
ls[1], ls[2], ls[3], ls[5] = 0, 2, 3, 5
for i in range(6, n + 1, 6):
f = i - 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
continue
f = i + 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
return filter(lambda x: x != 0, ls)
Ehrlich screening 1 0 8 10^8 108 Prime numbers with thein range of the approximately need 2 About minutes , I'm afraid it's too big to bear . So first 1 0 8 10^8 108 The prime number of , And greater than 1 0 8 10^8 108 Take out the prime number of . Get the results 1 0 8 10^8 108 The prime numbers within are 506733 individual . A large number is about 130 individual .
506733
[542693491967, 142787902577, 452440529173, 663634895869, 71242929179, 999870483413, 441673697183, 895134836909, 59008094959, 812048153483, 153230177243, 5986461211, 825268545161, 85386152959, 305669636917, 176618331487, 627185459239, 517233054923, 347714268719, 75380450897, 652349118967, 746710276723, 887316078643, 55623754253, 726602124691, 63723051253, 11944000489, 14326008041, 995344474081, 127374806651, 101228446879, 782792370337, 7616731547, 672817895497, 309261587441, 993510068537, 898280626321, 691250724803, 436362423451, 135244424501, 873959450791, 404517752423, 803431472291, 890481756773, 299729772337, 993254812121, 939705423281, 928689411767, 950796808643, 925182899009, 867933942403, 177084914339, 374154056921, 195931411013, 636268614181, 845966263637, 669349089677, 279219681547, 116772294307, 458677064359, 414099720659, 553029935971, 225122592047, 523383194647, 291752440213, 29190046721, 756126896941, 400963923179, 807339716593, 666619632839, 792597812483, 157223341237, 515677221383, 869902952023, 277744493561, 279840195947, 12066121523, 659914745389, 796743912131, 973038777059, 856703807231, 66169702601, 987064845247, 916671221021, 884623305749, 504935549881, 232438712231, 701919604183, 542037833447, 521942095081, 726449610001, 840499018589, 492469281101, 757165962919, 437417377471, 903288533789, 254110134101, 265121359891, 776841707227, 854559132599, 325401328397, 675731682791, 730947154187, 280786162939, 670729451441, 48996391291, 286681507897, 847973529401, 166381727761, 568868879153, 56085663143, 417414542761, 666771906149, 857635614683, 188918440631, 490214446741, 82741563491, 411523187461, 304024439243, 912661149107, 556591023551, 934801057481, 828742723319, 814141769183, 528476615281, 560425065263, 224638484077, 610321268093, 655599334577, 624348698849]
It is also quite frightening to directly judge whether these large numbers are prime numbers , So we can judge whether a super large number is a prime number , We have to use another method —— Fermat prime test . This is an algorithm I studied in my final assignment of algorithm class before , Is to use random numbers to randomly remainder large numbers , If you can divide , It's not prime ; Added an optimization , A coprime judgment is added , It greatly improves the efficiency and accuracy of the algorithm .
for p in bigNum:
K = 100 # The number of random number verification , The greater the number , The higher the accuracy . Actually measured K=10 You can get accurate results
k = 0
while k < K: # Here we use while It is used to determine whether the random completion rate is 100%
b = int(random.random() * (p - 1) + 1) # Generate a 1~p-1 Random integer between
factor = math.gcd(b, p) # Calculation b,p Maximum common divisor of
r = runFermatPower(b, p, p) # Calculation b^p mod p
print(f" The first {
k + 1} Take random number for times , random number b={
b}, {
b} and {
p} The greatest common divisor of is {
factor}, r=({
b}^{
p})mod p={
r}", end=', ')
if factor > 1:
print(f" because b={
b} And p={
p} The greatest common divisor of is {
factor}, Not coprime number , so p={
p} As composite ")
break
elif r != b:
print(f" because r={
r},({
b}^{
p}) mod p ={
r}!={
b}, so p={
p} As composite ")
break
else:
print(f" so p={
p} It could be prime ")
k += 1
if k == K:
print(f" after {
K} Second cycle verification , p={
p} It could be prime , n The probability of being a prime number is {
(1 - 1 / (2 ** k)) * 100}%")
Get the final result ：
506753
【 Complete code 】
The code in the course of the competition is step-by-step , Step by step , Then get the result and calculate the next step , This code is the optimized full version of the code , You can get the final result by running it directly .
B.py · AYO/Algorithm - Code cloud - Open source in China (gitee.com)
