Программа C++ для печати простых чисел от 1 до N

Опубликовано: 7 Октября, 2022

По заданному числу N необходимо вывести простые числа от 1 до N.

Примеры:

Input: N = 10
Output: 2, 3, 5, 7

Input: N = 5
Output: 2, 3, 5

Алгоритм:

  • Во-первых, возьмите число N в качестве входных данных.
  • Затем используйте цикл for для перебора чисел от 1 до N.
  • Затем проверьте, чтобы каждое число было простым числом. Если это простое число, выведите его.

Approach 1:  Now, according to the formal definition, a number ‘n’ is prime if it is not divisible by any number other than 1 and n. In other words, a number is prime if it is not divisible by any number from 2 to n-1.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N^2), пространственная сложность: O(1)

Approach 2:  For checking if a number is prime or not do we really need to iterate through all the number form 2 to n-1? We already know that a number ‘n’ cannot be divided by any number greater than ‘n/2’. So, according to this logic we only need to iterate through 2 to n/2 since number greater than n/2 cannot divide n.

Временная сложность: O(N^2), пространственная сложность: O(1)

Approach 3: If a number ‘n’ is not divided by any number less than or equals to the square root of n then, it will not be divided by any other number greater than the square root of n. So, we only need to check up to the square root of n.

Временная сложность: O(N^(3/2)), пространственная сложность: O(1)

Вы можете дополнительно оптимизировать временную сложность до O(n*log(log(n))).

Пожалуйста, обратитесь к полной статье о программе для печати простых чисел от 1 до N для получения более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ