Домашнее задание: простые числа

Я пытаюсь создать функцию bpr Isprime, которая создает список простых чисел, охватывающих целое число, вводимое пользователем, а затем линейно просматривает этот список и возвращает true, если входное целое в этом списке. У меня возникла проблема, однако, выясняя, как сделать список, который покрывает входное целое число (то есть, если пользователь вводит 4, список должен иметь 2,3 и 5).

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

bool Isprime(int N){
 int i,tprime=3;
 list<int>prime;
 prime.push_back(2);
 list<int>::iterator it;
 for (it=prime.begin();it!=prime.end();it++){
 if (*it</int></int>
<p> Можете ли вы, ребята, дать мне несколько советов о том, как сделать эту работу? Я могу найти линейный поиск.</p>
1 ответ

У вас есть список известных простых чисел, которые вы можете использовать для проверки каждого отдельного номера, чтобы узнать, является ли оно простым. Прямо сейчас вы пытаетесь перебрать этот список на внешний уровень. Это не кажется совершенно правильным.

Вот один из способов сделать это (совпадающий с тем, что вы пытались сделать):

  1. Подсчитайте от 3 до номера, который вы ищете.
  2. Определите максимальное основное значение, которое необходимо проверить (т.е. Квадратный корень из числа)
  3. Для каждого номера проверяйте, является ли это простым числом, определяя напоминание о его делении на каждый элемент списка известных простых чисел до максимального значения, которое необходимо проверить.
  4. Если число является простым, добавьте его в список известных простых чисел.

licensed under cc by-sa 3.0 with attribution.