Ускорить программу на Python

@jvf · Регистрация: 27.05.2017

Студворк — интернет-сервис помощи студентам

Есть простенькая задачка. Я её решил на C++, но на Python не получается, потому что язык более медленный, и не удаётся уложиться в 1 секунду. Но я знаю, что на Python также можно решить эту задачу. Но как?

1. Задача

Кликните здесь для просмотра всего текста

Простые числа
(Время: 1 сек. Память: 16 Мб Сложность: 25%)

Необходимо вывести все простые числа от M до N включительно.
Входные данные

Входной файл INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ 300 000)
Выходные данные

В выходной файл OUTPUT.TXT выведите все простые числа от M до N в порядке возрастания, по одному в строке. Если таковых чисел нет, то следует вывести «Absent».

Пример:
INPUT.TXT
2 5
OUTPUT.TXT
2
3
5

INPUT.TXT
4 4
OUTPUT.TXT
Absent

2. Решение на C++ (решение правильное)

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <fstream>
#include <iostream>
#include <math.h>
 
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
 
int find_prost(int a)
 
{
 
    if (a==2) 
        {return 1;};
 
    for (int i=2;i<sqrt(a)+1;i++){
 
 
        if ((a%i)==0){
 
            return 0;
        }
 
    }
 
    return 1;
 
 
}
 
int main(int argc, char* argv[])
{
    setlocale(LC_ALL, "rus"); // êîððåêòíîå îòîáðàæåíèå Êèðèëëèöû
    
    int m,n;
    
    ifstream fin("INPUT.TXT"); // îòêðûëè ôàéë äëÿ ÷òåíèÿ
 
    fin >> m;
    fin >> n;
 
    fin.close(); 
    //cout <<"m="<<m<<" n="<<n;
        
    ofstream fout("OUTPUT.TXT");
   
 
    //fout<< "Hello";
    //fout.close();
    
    bool find = false;
    int answer;
 
    
    for (int i=m;i<=n;i++){
 
        answer = find_prost(i);
        //cout<<"i="<<i<<"answer="<<answer<<endl;
 
        if (answer == 1) {
            find = true;
            fout << i<<endl;
        } 
 
    }
 
    if (find == false){
 
        fout << "Absent";
    }
 
    fout.close();
    //cout << a%2;
    //system("pause");
    
    return 0;
}

3. Решение на Python (не укладываюсь в 1 секунду)

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import math
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
def sum(x):
 
    sum = 0
 
    for n in range(1,x-1):
        sum += n*math.pow(2, x-2-n)
 
    return sum 
        
 
def find_prost(a):
 
    for i in range(2, int(math.sqrt(a))+1):
        #print("i=",i)
        if (a % i) == 0:
            #print("Наша ситуация")
            return 0
 
    return 1
 
"""
answer = find_prost(17)
 
found = False
 
for i in range(m,n+1):
    if sum(i)%i == 1 or i==2:
        found = True
        g.write(str(i)+" ")
 
if found == False:
    g.write("Absent")
"""
found = False
for i in range(m, n+1):
 
    if find_prost(i) == 1:
        found = True
        g.write(str(i)+" ")
 
if found == False:
    g.write("Absent")

@Vigi · 18.11.2017, 12:11

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_prim(n):
    return ~-2 ** n % n < 2
 
 
fl = 0
with open('INPUT.TXT', encoding='utf-8') as fr, open("OUTPUT.TXT", 'w', encoding='utf-8') as fw:
    m, n = map(int, fr.read().split())
    for digit in range(m, n + 1):
        if is_prim(digit):
            fw.write(str(digit) + '\n')
            fl += 1
 
if not fl:
    with open("OUTPUT.TXT", 'w', encoding='utf-8') as fw:
        fw.write('Absent')

@jvf · 18.11.2017, 12:15 **[ТС]**

Ваша программа не прошла 14 тест. Было потрачено 1,2 секунды на проверяющем сервере.

Но Ваша программа -- уже шаг вперёд по сравнению с моей. Моя программа на Python не прошла 12 тест. Ваша сделала два шага вперёд.

Нет, вру. Моя программа на Python прошла 15 тестов. А ваша только 14. То есть Ваша программа -- один шаг назад.

@Vigi · 18.11.2017, 12:26

ссылку можно на систему тестирования?

@jvf · 18.11.2017, 12:34 **[ТС]**

Вот ссылка:

Добавлено через 1 минуту
Ссылка была удалена автоматически движком этого сайта.

@Vigi · 18.11.2017, 13:20

и где ссылка?

@jvf · 18.11.2017, 13:26 **[ТС]**

Эта ссылка автоматически удаляется движком. Как её вставить?

@Vigi · 18.11.2017, 13:36

Тут

@jvf · 18.11.2017, 13:44 **[ТС]**

Добавлено через 6 минут
Эту ссылку движок cyberforum.ru удаляет автоматически. Я только что это сделал, и ссылка была удалена.

Вот ещё раз попробую. Надо поставить букву a перед cmp.ru

http://cmp.ru/asp/do/index.asp... roblem=853

@Vigi · 18.11.2017, 13:45

ок посмотрю

vic5710 · 18.11.2017, 15:16

а такой способ?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math
from time import time
 
n = int(input("Расчет простых чисел до числа: ")) + 1
t1 = time()
a = [True] * n
for i in range(2, int(math.sqrt(n))):
    for j in range(i * 2, n, i):
            a[j] = False
b = [i for i in range(2, n) if a[i]]
t2= time()
print('time:',t2-t1)
>>>
Расчет простых чисел до числа: 500000
time: 0.4987502098083496
>>>

@jvf · 18.11.2017, 16:21 **[ТС]**

В задаче нужно в диапазоне найти простые числа от m до n. А у вас простые числа от 2 до некого числа n.

Добавлено через 1 минуту
И компьютер на сервере намного слабее, чем ваш.

Добавлено через 7 минут
Пока мой лучший результат -- тест номер 15 (на этом тесте идёт завал). Итог 1,171 секунда. Мне нужно улучшить свой алгоритм на 0.171, чтобы пройти этот тест на Python.

vic5710 · 18.11.2017, 16:31

Сообщение от jvf

В задаче нужно в диапазоне найти простые числа от m до n. А у вас простые числа от 2 до некого числа n.

ну так поменяйте 2 на m

@jvf · 18.11.2017, 16:55 **[ТС]**

Вот поменял. К сожалению, ваша программа не проходит даже первого теста, если m=2 и n=5

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
from time import time
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
#t1 = time()
a = [True] * n
for i in range(2, int(math.sqrt(n))):
    for j in range(i * 2, n, i):
            a[j] = False
b = [i for i in range(m, n) if a[i]]
print(b)
t2= time()
 
if len(b) == 0:
    g.write("Absent")
else:
    for p in b:
        g.write(str(p)+" ")

Добавлено через 4 минуты
Ваша программа просто вообще неверная.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import math
from time import time
 
#n = int(input("Расчет простых чисел до числа: ")) + 1
n = 5
t1 = time()
a = [True] * n
for i in range(2, int(math.sqrt(n))):
    for j in range(i * 2, n, i):
            a[j] = False
b = [i for i in range(2, n) if a[i]]
t2= time()
print(b)
print('time:',t2-t1)
#>>>
#Расчет простых чисел до числа: 500000
#time: 0.4987502098083496
#>>>

Если n=5, то она даёт в ответ 4, что, очевидно, неверно (она даёт ответ 2,3,4). А должна давать следующий ответ: 2,3,5

vic5710 · 18.11.2017, 18:44

это ошибка округления

Python
1
2
#for i in range(2, int(math.sqrt(n))):
for i in range(2, int(math.sqrt(n)) + 1):

@jvf · 18.11.2017, 18:53 **[ТС]**

Задача решена. Поздравляю! Тест пройден!!!

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import math
from time import time
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
n += 1 
#t1 = time()
a = [True] * n
for i in range(2, int(math.sqrt(n))+1):
    for j in range(i * 2, n, i):
            a[j] = False
b = [i for i in range(m, n) if a[i]]
print(b)
t2= time()
 
if len(b) == 0:
    g.write("Absent")
else:
    for p in b:
        g.write(str(p)+" ")

Среднее время выполнения по всем тестам составило 0,656 секунды, средняя память -- 4796 Кб.

Кто-нибудь сможете предложить ещё более быстрый алгоритм?

vic5710 · 18.11.2017, 19:04

http://py-algorithm.blogspot.r... st_09.html

@jvf · 18.11.2017, 20:24 **[ТС]**

Предыдущий вариант показал среднее время в 0,656 секунды по 15-ти или 20-ти тестам. Всего лишь одна строчка улучшает скорость в два раза.

Добавление:

Python
1
2
    if a[i] == False:
        continue

Приводит к тому, что среднее время работы по 15-ти или 20-ти тестам алгоритма уменьшается до 0,312 секунды. Одна строчка -- поразительное увеличение производительности алгоритма.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import math
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
n += 1
a = [True] * n
#print(a)
 
for i in range(2, int(math.sqrt(n))+1):
    if a[i] == False:
        continue
 
    for j in range(i * 2, n, i):
            a[j] = False
 
#print(a)
b = [i for i in range(m, n) if a[i]]
#print(b)
#t2= time()
 
if len(b) == 0:
    g.write("Absent")
else:
    for p in b:
        g.write(str(p)+" ")

vic5710 · 18.11.2017, 20:37

у меня быстрее всего работает вариант с set

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def primes(N):
  s = set(range(2, N))
  for i in range(2, math.ceil(math.sqrt(N))):
    if i in s:
      s -= set(range(2*i, N, i))
  return s
 
while True:
    n = int(input("Расчет простых чисел до числа: ")) + 1
    if n == 1: break
    t1 = time()
    s = primes(n)
    print (time() -t1)

Python
1
2
3
4
5
6
>>>
Расчет простых чисел до числа: 1000000
0.41737818717956543
Расчет простых чисел до числа: 300000
0.12035417556762695
>>>

@jvf · 18.11.2017, 21:03 **[ТС]**

Вот ваш вариант с множествами (возможно, его можно улучшить) -- он не засчитывается, потому что автоматическая система проверки на сервере пишет, что превышен лимит памяти. 19 Mb (на 15-том тесте). Тот вариант, который был ранее, засчитан, потому что и по времени уложился, и памяти занимает не так много: всего 4 Мб.

Там есть и ограничение по памяти, не более 16 Мб.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import math
from time import time
 
def primes(N):
  N += 1
  s = set(range(2, N))
  for i in range(2, int(math.ceil(math.sqrt(N)))+1):
    if i in s:
      s -= set(range(2*i, N, i))
  return s
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
s = primes(n)
b = [x for x in s if x>=m]
found = False
for c in b:
  g.write(str(c)+" ")
 
if len(b) == False:
  g.write("Absent")

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	18.11.2017, 12:15 [ТС]
	Ваша программа не прошла 14 тест. Было потрачено 1,2 секунды на проверяющем сервере. Но Ваша программа -- уже шаг вперёд по сравнению с моей. Моя программа на Python не прошла 12 тест. Ваша сделала два шага вперёд. Нет, вру. Моя программа на Python прошла 15 тестов. А ваша только 14. То есть Ваша программа -- один шаг назад. 0

@Vigi 641 / 481 / 179 Регистрация: 28.05.2012 Сообщений: 1,419
	18.11.2017, 12:26
	ссылку можно на систему тестирования? 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	18.11.2017, 12:34 [ТС]
	Вот ссылка: Добавлено через 1 минуту Ссылка была удалена автоматически движком этого сайта. 0

@Vigi 641 / 481 / 179 Регистрация: 28.05.2012 Сообщений: 1,419
	18.11.2017, 13:20
	и где ссылка? 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	18.11.2017, 13:26 [ТС]
	Эта ссылка автоматически удаляется движком. Как её вставить? 0

@Vigi 641 / 481 / 179 Регистрация: 28.05.2012 Сообщений: 1,419
	18.11.2017, 13:36
	Тут Миниатюры 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	18.11.2017, 13:44 [ТС]
	Добавлено через 6 минут Эту ссылку движок cyberforum.ru удаляет автоматически. Я только что это сделал, и ссылка была удалена. Вот ещё раз попробую. Надо поставить букву a перед cmp.ru http://cmp.ru/asp/do/index.asp... roblem=853 0

@Vigi 641 / 481 / 179 Регистрация: 28.05.2012 Сообщений: 1,419
	18.11.2017, 13:45
	ок посмотрю 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	18.11.2017, 16:21 [ТС]
	В задаче нужно в диапазоне найти простые числа от m до n. А у вас простые числа от 2 до некого числа n. Добавлено через 1 минуту И компьютер на сервере намного слабее, чем ваш. Добавлено через 7 минут Пока мой лучший результат -- тест номер 15 (на этом тесте идёт завал). Итог 1,171 секунда. Мне нужно улучшить свой алгоритм на 0.171, чтобы пройти этот тест на Python. 0

vic5710 963 / 718 / 276 Регистрация: 10.12.2016 Сообщений: 1,764
	18.11.2017, 19:04
	http://py-algorithm.blogspot.r... st_09.html 1