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

Question

У меня есть ряд случайных чисел. Диапазон фактически определяется пользователем, но это будет до 1000 целых чисел. Они размещены в этом:

vector<int> n

и значения вставляются следующим образом:

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

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

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

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

Этот метод обычно работал, когда у меня только что была серия чисел от 0 до 1000, но, похоже, он не работает сейчас, когда у меня есть номера не по порядку и дубликаты. Есть ли лучший способ найти не простые числа в векторе? Я испытываю желание просто создать еще один вектор, заполнить его n числами и просто найти непростые числа таким образом, но будет ли это неэффективным?

Хорошо, поскольку диапазон составляет от 0 до 1000, мне интересно, проще ли просто создать вектор с отсортированным по 0-n, а затем с помощью сита найти простые числа?

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}

Answer 1

В этом коде:

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

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

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

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

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

Answer 6

Идея сита, который вы пытаетесь реализовать, зависит от того, что вы начинаете с простого числа (2) и вычеркиваете множество из этого числа - так что все числа, которые зависят от простого числа & "2 Quot; исключены заранее.

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

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

Answer 7

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

<Ол>

Если вы хотите проверить, является ли ваш номер простым или непростым, вам нужно проверить v [j]% i == 0, а не наоборот

Вы не проверяли, делится ли ваш номер сам по себе

Вы продолжаете проверять свои номера снова и снова. Это очень неэффективно.

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

Таким образом, псевдо-код 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;
   }
}

Answer 8

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

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

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

Answer 9

Джереми прав, основная проблема в том, что ты 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], а не только до квадратного корня из <=>. И это попытка деления на все числа, а не только на простые числа.

Но это будет работать.