程序必须接受 N 个整数作为输入。对于N个整数中的每个整数值X，程序必须打印可以与整数X相加的最小值(可能为零)，以便该整数成为素数
Boundary :
1<=N<=2,00,000
2<=Each Int<=10^6
TimeLimit : 100 ms
我的代码:
def isPrime(n) :
if (n <= 1) :
return False
if (n <= 3) :
return True
if (n % 2 == 0 or n % 3 == 0) :
return False
i = 5
while(i * i <= n) :
if (n % i == 0 or n % (i + 2) == 0) :
return False
i = i + 6
return True
def summ(g):
for i in range(20):
if isPrime(g+i):
return i
n = int(input())
print(*(summ(i) for i in list(map(int,input().split()))))
示例:
Input :
7
89 54 36 74 44 19 12
Output:
0 5 1 5 3 0 1
我的代码没有错误，并且我使用了优化方法来查找整数是否为素数，但仍然超出了N == 100,000的时间限制> 有什么办法可以将时间限制减少到100毫秒
最坏的情况是
n=200,000
[169988', '865748', '818394', '160754', '532538', '44700', '607214', '404390', '405894', '954978', '115734', '871022', '762398', '744128', '394638', '981440', '966030', '515540', '859578', '116240', '534858', '263984', '159408', '333930', '310728', '949262', '580734', '40032', '289244', '130052', '921200', '452534', '58632', '689964', '250920', '126224', '845184', '806088', '867734', '662370', '204668', '3728', '193164', '187964', '477260', '365138', '21194', '334760', '46272', '401244', '239934', '670490', '894330', '408770', '766068', '129968', '702828', '354464', '396834', '905340', '586770', '543860', '923388', '197610', '809834', '862344', '194204', '609278', '7874', '411158', '701220', '78780', '525980', '949812', '58700', '829224', '885608', '38630', '507372', '866330', '12918', '292058', '143978', '801290', '97460', '746118', '625610', '48590', '182124', '127952', '545388', '922638', '268050', '801488', '613290', '276278', '387138', '664442', '519588', '418812', '536532', '755570', '283832', '92004', '66890', '724520', '11594', '134742', '542684', '169910', '37022', '689762', '633878', '640968', '277550', '839162', '953150', '742370', '219954', '271058', '846722', '22398', '237930', '637712', '46220', '868740', '9872', '573108', '399720', '114810', '262194', '122100', '104712', '494354', '791804', '279110', '484544', '89460', '797682', '875298', '740522', '218510', '188954', '337794', '375158', '296160', '172604', '871958', '451362', '746414', '757344', '657894', '60734', '485732', '213650', '206300', '716858', '101064', '118820', '185750', '332264', '93288', '363590', '555828', '120284', '814008', '954912', '513698', '795002', '384344', '116960', '866738', '926660', '998528', '170384', '569244', '695504', '77864', '469070', '38784', '47388', '358484', '533738', '966432', '126714', '440822', '964040', '808958', '698388', '157428', '338412', '332208', '976514', '25794', '251540', '399872', '765468', '331142', '454722', '263958', '51614', '694080', '422268', '14754', '661268', '479798', '647402', '198842', '896112', '346562', '72354', '106950', '516234', '313154', '60728', '244640', '345732', '215768', '75980', '349110', '589140', '950690', '476888', '246540', '150908', '291104', '42768', '82470', '751278', '366678', '806904', '741080', '356094', '206828', '850388', '270338', '649218', '10274', '48884', '935814', '978750', '892628', '212678', '163212', '133650', '883974', '665294', '806762', '876824', '8838', '697262', '403434', '114408', '382862', '351438', '969342', '79802', '645000', '113028', '349338', '354150', '384548', '20564', '465644', '721452', '607418', '575250', '940032', '463890', '579282', '862992', '847664', '896634', '828408', '847202', '443940', '879114', '418512', '997202', '690104', '770184', '594750', '851034', '447108', '640650', '271218', '990762', '493920', '594642', '852830', '191562', '794994', '117390', '672902', '978018', '59772', '842450', '153818', '139362', '712302', '437862', '263724', '201894', '575220', '481640', '242010', '466730', '997370', '128450', '174222', '109904', '455970', '564498', '534740', '340802', '358074', '796152', '97022', '630024', '221874', '950738', '730592', '907394', '566988', '580982', '155502', '425520', '908808', '199374', '491498', '50232', '107468', '857322', '728628', '477410', '430290', '643458', '642582', '612714', '705560', '834470', '775344', '55734', '782088', '13800', '432344', '146778', '518412', '450600', '163322', '854958', '30894', '872090', '855734', '304212', '535124', '68438', '734480', '532752', '547038', '366522', '424268', '644364', '152658', '17402', '932750', '465008', '807540', '670730', '205398', '988850', '779900', '231968', '746024', '678612', '319682', '357564', '521982', '363902', '487692', '880730', '340958', '807338', '540612', '38012', '21912', '657500', '836570', '647430', '884294', '470078', '875114', '266354', '721058', '853970', '265872', '795102', '788078', '451580', '169952', '997268', '147648', '185768', '286802', '408744', '459230', '33108', '490004', '27998', '123050', '153702', '151142', '543828', '18798', '498104', '459842', '895314', '119298', '787712', '197424', '918752', '82268', '443732', '839430', '134334', '570392', '16964', '537242', '149112', '500180', '531912', '556944', '942860', '892862', '518690', '330612', '904088', '746678', '310232', '876374', '345908', '889280', '619188', '808994', '658212', '248888', '135572', '55890', '741342', '512538', '55932', '251622', '12228', '687458', '48342', '310364', '345228', '436158', '72720', '634688', '179990', '527942', '939924', '68042', '902502', '295334', '9414', '203354', '758112', '134918', '661482', '948174', '476082', '75330', '94874', '825108', '78008', '833048', '647588', '951278', '857714', '970538', '248628', '141444', '477768', '464814', '514278', '53234', '866714', '455514', '188300', '90620', '206624', '259682', '13760', '77154', '272772', '58604', '358880', '522080', '914240', '644790', '1700', '381570', '955278', '429242', '713192', '745934', '961100', '480584', '352250', '658488', '929808', '224430', '52584', '915974', '147180', '953112', '585792', '212058', '915144', '953502', '756704', '800144', '143138', '96780', '303890', '557282', '999050', '680658', '446934', '304962', '211868', '308928', '42452', '578484', '853320', '671358', '780050', '196908', '983930', '950810', '65124', '489794', '391250', '708284', '351078', '34920', '116868', '397634', '19604', '867620', '547770', '746792', '503624', '245630', '62202', '222008', '207470', '674162', '136538', '130100', '452042', '384488', '432662', '280352', '570192', '905652', '529808', '33410', '482622', '992372', '28278', '196202', '170778', '874772', '80538', '450842', '532452', '164430', '411992', '456960', '32942', '934002', '565248', '973760', '469770', '280298', '21384', '807474', '254520', '235242', '633938', '873404', '687180', '305472', '377844', '110850', '289848', '969444', '812138', '558422', '334932', '630920', '276444', '483140', '951362', '720092', '286814', '503054', '727668', '587520', '307512', '448598', '332952', '7322', '721014', '869900', '278690', '169244', '763494', '358314', '438828', '23628', '241982', '672044', '499854', '4458', '191510', '814328', '728874', '948090', '327344', '957332', '116868', '879170', '442208', '113024', '11312', '446190', '847934', '792108', '307578', '60938', '987660', '26628', '996600', '21882', '580170', '877940', '633470', '388692', '7938', '543608', '806372', '544938', '819150', '439788', '393630', '126962', '662714', '595962', '759180', '76718', '731118', '514890', '125222', '384438', '645684', '268884', '608118', '537374', '500258', '90584', '27774', '195992', '872090', '923712', '24692', '600360', '571854', '863120', '718304', '29790', '107508', '717428', '52070', '609374', '208254', '1230', '92684', '51488', '986114', '798228', '951080', '944310', '582458', '182058', '41958', '488922', '101604', '302010', '459182', '912344', '868874', '1298', '166350', '531638', '219282', '99000', '689412', '809604', '60398', '814008', '211658', '357672', '26628', '874824', '520380', '38288', '105608', '581730', '978474', '972684', '4598', '92762', '2162', '630912', '225242', '663654', '145220', '517824', '999102', '414312', '211502', '833310', '541712', '379724', '902600', '277494', '607038', '329432', '757364', '784628', '25170', '282428', '35324', '932664', '455402', '796260', '540588', '606302', '22434', '128340', '10464', '138684', '34614', '534342', '660120', '271068', '346440', '959370', '178118', '256020', '10772', '657708', '781044', '228678', '311882', '488', '510452', '327444', '875712', '647964', '869438', '121260', '579504', '532920', '938342', '540438', '784548', '260922', '186480', '653820', '163772', '130364', '959490', '810194', '812250', '375252', '168458', '476478', '838694', '257372', '311420', '615068', '961118', '950634', '702018', '408804', '111494', '591752', '467472', '599742', '374118', '509222', '283008', '91250', '362852', '718974', '580734', '755318', '920790', '908582', '72224', '936054', '698670', '892604', '510332', '171618', '688680', '299018', '864290', '426998', '663410', '710372', '521642', '43952', '389798', '753984', '107310', '81902', '915380', '883490', '275912', '70452', '702102', '170958', '479570', '269210', '871160', '158792', '473288', '345432', '758930', '848850', '725910', '557694', '515598', '30638', '571370', '189068', '294704', '793548', '745118', '832478', '615722', '156362', '854364', '688160', '363152', '631938', '236682', '460464', '36068', '269982', '634344', '348210', '249974', '324774', '705534', '79394', '122850', '694082', '346878', '704688', '880514', '77558', '647790', '39954', '635354', '407948', '3080', '131448', '365760', '533672', '923948', '657072', '565668', '324294', '105692', '762780', '342972', '591090', '752994', '815520', '216732', '99714', '114278', '480072', '632994', '684978', '666770', '997740', '820578', '293640', '411194', '446294', '550490', '933968', '443868', '13298', '214010', '46818', '182060', '383694', '955608', '515612', '717884', '1302', '739494', '572834', '264464', '947652', '565464', '496748', '574160', '651462', '186708', '957212', '464910', '638568', '22470', '238748', '830888', '239964', '94350', '830580', '561104', '403788', '28352', '433370', '943752', '160982', '262338', '641262', '404558', '720060', '171264', '972330', '380198', '351402', '287150', '633474', '338390', '33354', '534404', '169322', '372060', '692730', '52364', '652358', '74204', '419088', '499524', '513158', '648342', '718358', '294564', '335610', '8630', '652658', '408624', '339762', '786420', '73304', '379188', '527348', '148914', '430752', '644198', '200088', '957098', '340284', '278414', '162692', '883878', '335528', '694368', '192818', '96908', '754968', '222008', '653622', '552710', '721208', '300234', '592854', '382650', '336042', '445878', '148868', '217970', '489990', '9030', '443604', '829988', '224712', '187508', '1784', '735422', '600338', '52164', '182142', '582794', '412950', '447678', '869070', '597270', '172002', '625410', '894404', '769620', '53820', '103484', '852990', '332804', '895320', '361512', '331502', '187928', '771218', '66702', '580530', '725808', '530262', '828524', '814644', '877404', '621740', '592484', '442754', '791952', '186552', '9750', '50924', '742608', '794594', '241454', '379178', '177044', '43332', '702828', '426744', '302928', '349914', '656600', '311982', '254700', '376758', '85782', '893220', '337284', '308142', '443040', '615314', '95084', '893568', '127740', '306030', '390782', '90002', '286290', '155664', '723960', '650564', '64680', '482124', '700362', '806858', '217082', '672884', '173714', '489102', '174458', '432054', '241952', '240422', '439800', '611484', '937502', '286928', '371360', '473504', '961134', '10134', '412538', '456350', '945962', '673550', '862418', '426198', '809424', '152810', '931878', '698978', '243840', '473378', '630102', '665222', '351932', '538598', '819812', '53454', '526652', '91944', '473328', '505694', '93494', '511898', '996884', '100610', '787808', '946460', '589328', '317732', '617768', '730188', '554532', '309108', '818430', '170810', '316214', '17342', '855620', '933422', '987798', '939452', '42900', '185492', '970878', '403688', '2544', '157890', '269210', '536672', '9042', '305862', '615188', '143528', '867734', '16128', '182', '210462', '540804', '504390', '880872', '73422', '20232', '606380', '668154', '66404', '507140', '121622', '950334', '157680', '170844', '514562', '110588', '239384', '390114', '733374', '6222', '400754', '746414', '106020', '675974', '325518', '389570', '377790', '800874', '831168', '21408', '612612', '599244', '729614', '486768', '365852', '588738', '897008', '983318', '728994', '71414', '352742', '960738', '220404', '754302', '95604', '581558', '85082', '602040', '473444', '907470', '608498', '26634', '434510', '358230', '327402', '713564', '421350', '528392', '647838', '855672', '717668', '182048', '293484', '179820', '117530', '143528', '754532', '399044', '649262', '895244', '582018', '25764', '655718', '918890', '879798', '511172', '154098', '92204', '897882', '120504', '2790', '1500', '285674', '24152', '196728', '192588', '705644', '779082', '876722', '549644', '532404', '761928', '998540', '311792', '66960', '77478', '191232', '181838', '146678', '549944', '315698', '250920', '576882', '955334', '318824', '620492', '29412', '193608', '16092', '95582', '405818', '765104', '975900', '20850', '474788', '934598', '725520', '683358', '988902', '900624', '728948', '181362', '690120', '155382', '450422', '292460', '60590', '1784', '210128', '952670', '966212', '212124', '313344', '267498', '522000', '510050', '623478', '309092', '133968', '739202', '400314', '866400', '226484', '7220', '692250', '462444', '443190', '846578', '458070', '432924', '304430', '915642', '940760', '402342', '463680', '932022', '508302', '989798', '74288', '360008', '138060', '257540', '80898', '555684', '12792', '678578', '147254', '59264', '16488', '171518', '275340', '5642', '446262', '509522', '279680', '750312', '496314', '193800', '938808', '693878']
我无法复制所有 200,000 个整数
最佳答案
这是一种可能的解决方案。它生成一个素数列表，直到输入数字的最大值，然后使用二分搜索查找相对于每个输入数字的下一个最大素数，最后计算这些值与输入之间的差:
from math import sqrt
def sieve(prime, n, primes):
for i in range(prime*prime, n+1, prime):
primes[i] = False
return primes
def listPrimes(n):
n = n * 2 # to allow for the largest input value not being prime
primes = [False, False] + [True] * (n - 1)
primes = sieve(2, n, primes)
q = int(sqrt(n))
for p in range(3, q+1, 2):
if primes[p]:
primes = sieve(p, n, primes)
return [p for p in range(n+1) if primes[p]]
def findNextPrime(n, primes):
i = len(primes) // 2
if primes[i] >= n:
if i == 0 or primes[i-1] < n:
return primes[i]
return findNextPrime(n, primes[:i])
return findNextPrime(n, primes[i:])
nums = [89, 54, 91, 74, 44, 19, 12]
primes = listPrimes(max(nums))
nextPrimes = [findNextPrime(n, primes) for n in nums]
delta = [np - p for p, np in zip(nums, nextPrimes)]
print(delta)
输出:
[0, 5, 1, 5, 3, 0, 1]
更新
正如 @PresidentJamesK.Polk 在评论中指出的那样，通过预先计算每个数字与下一个素数之间的差异可以提高效率。这可以通过不过滤筛子，然后以相反的顺序遍历它来计算每个数字到下一个素数的距离来完成:
from math import sqrt
def sieve(prime, n, primes):
for i in range(prime*prime, n+1, prime):
primes[i] = False
return primes
def listPrimes(n):
n = n * 2 # to allow for the largest input value not being prime
primes = [False, False] + [True] * (n - 1)
primes = sieve(2, n, primes)
q = int(sqrt(n))
for p in range(3, q+1, 2):
if primes[p]:
primes = sieve(p, n, primes)
return primes
def primeDiffs(primes):
primediffs = []
i = len(primes) - 1
while not primes[i]:
i -= 1
for i in range(i, -1, -1):
if primes[i]:
dist = 0
else:
dist += 1
primediffs.append(dist)
return primediffs[::-1]
nums = [89, 54, 36, 74, 44, 19, 12]
primes = listPrimes(max(nums))
diffs = primeDiffs(primes)
delta = [diffs[n] for n in nums]
print(delta)
输出:
[0, 5, 1, 5, 3, 0, 1]
注意
对于这两种情况，应在输入数字时计算 max(nums) 以节省时间。
关于python-3.x - 质数和最小值 - 超出 python 时间限制，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62463776/