Простое целое число - добавить наименьшее значение - превышение лимита времени python - PullRequest
Новая
       86

Простое целое число - добавить наименьшее значение - превышение лимита времени python

2 голосов
/ 19 июня 2020

Программа должна принимать N целых чисел в качестве входных данных. Для каждого целого значения X среди N целых чисел программа должна вывести наименьшие значения, которые можно добавить к целому числу 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

В моем коде нет ошибок, и я использовал способ optimised, чтобы узнать, является ли целое число является простым или нет, но я все равно получаю превышение лимита времени для 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']

Я могу ' t скопируйте все 200000 целых чисел

Ответы [ 2 ]

2 голосов
/ 19 июня 2020

Вот одно из возможных решений. Он генерирует список простых чисел до максимального значения входных чисел, затем использует двоичный поиск, чтобы найти следующее по величине простое число относительно каждого входного числа, наконец вычисляя разницу между этими значениями и входными данными: 

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), поскольку числа вводятся для экономии времени.

1 голос
/ 20 июня 2020

Вот быстрый способ сделать это: быстрее, чем 100 мс для каждого элемента, но медленнее для полного набора (даже просеивание занимает больше 100 мс, и это быстрый алгоритм): 

from sympy import isprime
import random
import numpy as np

def primes_sieve2(limit):
    a = [True] * limit
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):
                a[n] = False

PRIMES=np.array(list(primes_sieve2(2750160)), 'uint32')

def create_random_array(limit=len(PRIMES)):
  vv = np.zeros(len(PRIMES), 'uint32')
  for x in range(limit-1):
     vv[x] = random.randint(0,pow(10,6))
  return vv

vv = create_random_array()
vvx = np.zeros(len(PRIMES), 'uint32')
count = 0
for xx in vv:
    vvx[count] = PRIMES[np.argmax(PRIMES > xx)] - xx
    count+=1

vvisprime = np.zeros(len(PRIMES), 'bool')
for x in range(len(PRIMES)):
   vvisprime[x] = isprime(int(vvx[x]) + int(vv[x]))



In [49]: vvx                                                                                                                                                   
Out[49]: array([ 5, 10, 13, ..., 12,  2,  2], dtype=uint32)

In [48]: vvisprime                                                                                                                                             
Out[48]: array([ True,  True,  True, ...,  True,  True,  True])
...