Нахождение составных чисел

В этом коде:

if(i % v[j] == 0)
  cout << v[j] << endl;

Вы тестируете свой индекс, чтобы увидеть, делится ли он на v [j]. Я думаю, вы хотели сделать наоборот, а именно:

if(v[j] % i == 0)

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

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

Во-вторых, для внешнего цикла вам действительно нужно перейти к sqrt (n), а не к n.

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

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

Генерация простых чисел лучше всего выполняется ситом Erathostenes Sieve - можно найти множество примеров этого алгоритма.

Вам следует попробовать использовать простое сито. Вам нужно знать максимальное число для создания сита (O(n)), а затем вы можете построить набор простых чисел в этом диапазоне (O(max_element) или, как указано в задаче O(1000) == O(1))) и проверить, входит ли каждое число в набор простых чисел.

Ваш код просто неправильный. Во-первых, вы тестируете i% v [j] == 0, который является обратным и также объясняет, почему вы получаете все числа. Во-вторых, ваш вывод будет содержать дубликаты, поскольку вы тестируете и выводите каждый входной номер каждый раз, когда он не проходит (сломанный) тест на делимость.

Другие предложения:

Использование n в качестве максимального значения в векторе и количества элементов в векторе сбивает с толку и бессмысленно. Вам не нужно передавать количество элементов в векторе - вы просто запрашиваете размер вектора. И вы можете довольно быстро вычислить максимальное значение (но если вы знаете его заранее, вы можете также передать его).

Как упоминалось выше, вам нужно только проверить sqrt (n) [где n - максимальное значение в векторе]

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

Если вы собираетесь тестировать каждое число индивидуально (я полагаю, используя обратное сито), я предлагаю тестировать каждое число индивидуально, по порядку. ИМХО это будет легче понять, чем то, как вы это написали - проверка каждого числа на делимость на k ‹n для постоянного увеличения k.

Идея решета, которую вы пытаетесь реализовать, зависит от того факта, что вы начинаете с простого (2) и вычеркиваете множество этого числа, поэтому все числа, зависящие от простого числа «2», заранее исключаются.

Это потому, что все непростые числа можно разложить на простые числа. В то время как простые числа не делятся по модулю 0, если вы не разделите их на 1 или сами по себе.

Итак, если вы хотите положиться на этот алгоритм, вам понадобится какое-то средство для фактического восстановления этого свойства алгоритма.

У вашего кода много проблем:

1. Если вы хотите проверить, является ли ваше число простым или непростым, вам нужно будет проверить v [j]% i == 0, а не наоборот.
2. Вы не проверяли, делится ли ваше число само по себе
3. Вы продолжаете проверять свои числа снова и снова. Это очень неэффективно.

Как предлагали другие ребята, вам нужно сделать что-то вроде Решета Эратосфена.

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

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}

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

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

затем пойти с ситом - как говорили другие

Джереми прав, основная проблема - это ваш i % v[j] вместо v[j] % i.

Попробуй это:

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

Это не оптимально, потому что оно пытается разделить на все числа меньше v[j], а не только на квадратный корень из v[j]. И это попытка деления на все числа, а не только на простые числа.

Но это сработает.