Compound Number Search

Question

I have a number of random numbers. The range is actually user-defined, but it will be up to 1000 integers. They fit into this:

vector<int> n

and the values ​​are inserted as follows:

srand(1);

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

I create a separate function to find all non-zero values. That's what I have now, but I know that this is completely wrong, because I get both simple and compound in the series.

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

This method usually worked when I just had a series of numbers from 0-1000, but it doesn't seem like it will work now that I have numbers from order and duplicates. Is there a better way to find non-empty numbers in a vector? I am tempted to just create another vector, fill it with n numbers and just find nonproliferation of primes like that, but will it be inefficient?

, 0-1000 , 0- , , , ?

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

, , , .

, , ( sqrt), .

Erathostenes Sieve - .

Answer 4

. (O(n)), (O(max_element) O(1000) == O(1))) , .

Answer 5

. -, i% v [j] == 0, , , . -, , () .

:

n . - . ( , ).

, sqrt (n) [ n - vecotr]

n, , . , - .

(, , ), . , , , , - k < n k.

Answer 6

, , , (2) - , "2", .

, . 0, 1 .

, , , .

Answer 7

, , :

• , -, v [j]% == 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;
    }
  }
}

This is not optimal, because he is trying to divide by all numbers less v[j], and not just the square root of v[j]. And he is trying to divide by all numbers instead of prime numbers.

But it will work.