Поиск составных чисел

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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

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

Answer 7

Ваш код, кажется, есть много проблем:

1. Если вы хотите, чтобы проверить, если ваше число простое или не простое, вы должны проверить V [у]% 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 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] вместо того, чтобы просто до квадратного корня из v[j]. И он пытается делить на все числа вместо простых чисел.

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