Решаю задачу, условие на скрине и во втором P.S. .

Для граничного теста (n=10000) время больше двух секунд. Что делать?
P.S. https://pastebin.com/9AUCm7hd
P.S. Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23,...
Напишите программу, которая выведет все простые числа на отрезке [1,n] в порядке возрастания.
Входные данные
В единственной строке входных данных записано целое число n (1 ≤ n ≤ 10000).
Выходные данные
Выведите все простые числа на отрезке [1,n] по возрастанию по одному в строке.
Пример(ы)
input.txt
25
output.txt
2
3
5
7
11
13
17
19
23

решето эратосфена

1. У меня твой код работает гораздо быстрее, за 16 мс. Ты с флагом -O2 компилировал? 2. Алгоритм асимптотически неоптимален

Да в коде вроде и так оно

В коде N раз запускается проверка на простоту

???

А зачем short?

задача в списке тех, которые можно решить без массивов, и я чёт хз как можно именно реализовать вычёркивание элементов без массивов). Если руководствоваться https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

Почему бы не вынести проверку на простоту в отдельную функцию? Имхо, так год становиться более читаемым

Ну, заведи массив и вычеркивай. Кажется, памяти на это с запасом хватит

Мм ну выводить из сразу?

я хз как visual studio компилит автоматически, я пробовал не debug версию, а release, такой же результат.

там 1 <= n <= 10000, поэтому я для экономии памяти выбрал его

Ну я бы попробовал g++.

там, где я решаю, в списках компиляторов ток visual studio c++ 2010, и я хз что под этим подразумевается и как он компилит)

https://brestprog.by/topics/factorization/

Спасибо большое, годная статья!

?

А разве это не будет дольше из-за вызовов функций?

Да фигню сказанул

Скорее всего, компилятор в режиме релизной сборки догадается подставить код функции проверки внутрь мейна. К тому же затраты на вызов функции пренебрежимо малы по сравнению с той работой, которую она должна совершить.

В плюсах же вроде можно inline помечать

Как я понял решето эратосфена работает следующим образом: создаём массив с числами от 2 до n включительно, вычёркиваем каждый второй начиная с 2^2, затем каждый третий начиная с 3^2, и так вычёркивать начиная с i^2, пока он меньше n.

Ну только делать это надо не для каждого i, а только для простых

Это можно сделать если i пустить по массиву, т.к. он будет подчищаться и каждый следующий i-ый будет простой (смотрел на гифку из википедии по ссылке выше в разделе алгоритм).