Жизненное

[nio]

На вопрос «напишите на листочке программу на любом языке программирования, которая находит простые числа от 1 до миллиона» ты, как и я, напишешь ответ в три строки: полным перебором. А потом на вопрос «а ускорьте ее в два раза» станешь, как я, вспоминать курс высшей математики, морщить лоб и мямлить, что не совсем помнишь алгоритм поиска простых чисел. Про то, что можно просто выбросить из перебора четные числа вспомнишь только вечером.

(С)с Хабра

Comments

[Менеджер Медуза]

А разве простые числа это не те, которые делятся без остатка только на себя и на 1?

[Менеджер Медуза]

www.ega-math.narod.ru/Liv/Zagier.htm
Теперь я не могу не написать программу =3
Только моих знаний в математике еще маловато =(
Ну, вот и получу!

[Гость]

Главное, не выбросить 2.

[Менеджер Медуза]

Я почти придумал как сделать прогу, которая будет определять, простое число или нет.
Я уверен что начало будет таким:
a = STDIN.gets
(2..(a - 1)).to_a
А дальше надо, чтобы выполнилось действие (я пока что не знаю как это точно написать, надо побольше прочитать про массивы):
a % (2..(a - 1)).to_a
А дальше нужно сделать так, чтобы при получение остатка 0 писало, что число не простое.
Ну и конечно же сделать цикл, который будет спрашивать "Do you want continue? y/n" =3

[Менеджер Медуза]

Вот начало:
b = STDIN.gets.chomp()
puts (2..(b.to_i - 1)).to_a

[nio]

Это какой язык?

[Менеджер Медуза]

Рубин. Ruby.

[Менеджер Медуза]

Я придумал как еще мне можно ее написать, только мне требуется время, которого у меня нет.

[Гость]

> напишите на листочке программу на любом языке программирования, которая находит простые числа от 1 до миллиона

Хм... Пожалуй, перебором проще всего.

N = 1000000
a = [True] * (N+1)
for i in xrange(2, N+1):
    if a[i]:
        print i
        a[i::i] = [False] * int(N/i)

> а ускорьте ее в два раза

На листочке? Нереально! Выкидывание чётных чисел даст всего-то ~20%.

Хотя это — python2. А если на «любом языке программирования», то:

primes(2, 1000000)

Наверняка найдётся язык, в котором есть функция primes.

[Менеджер Медуза]

Ой, а я уже целиком и полностью забыл об этом. Сейчас срубим ее.

[nio]

Гм, товарищи, всегда интересовало: а чем вас привлекают такие эзотерические языки? Почему не C/С++, не Java, не Pascal/Delphi, не Basic?

[Менеджер Медуза]

Я как бы начинающий, так что я начал с Ruby, поскольку он простой, но и с очень широкими возможностями, а С++ я немного учил, но перейду к нему гораздо позже.

[Менеджер Медуза]

Готово:
puts "1"
def solve
x = 1
loop do
x = x + 1
y = 1
loop do
y = y + 1
if y == x
puts x
end
break if x%y == 0
#break if y == x - 1 || x % y == 0
end
break if x == 100
end
end

solve

Оно находит простые числа от 1 до 100, но если сделать break if x == 1000000, то все будет супер.

Я изобрел способ нахождения простых чисел, я - молодец!

[nio]

Император Медуза, но это же тоже полный перебор... Долго будет работать. Решето Эратосфена и то быстрее.
Ладно, фиг с ним.

[Менеджер Медуза]

У меня практически мгновенно выдает. Могу написать на С++, тогда быстрее будет.