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

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

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;
   }
}

Answer 9

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

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

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