Question regarding primes in array

[gevCplus]

Hello all,

I am trying to spot all the prime numbers within an array however my code, apart from the prime numbers it gives me an some non-prime numbers as well (i.e from 2 - 10 it gives a 9). Any advice?

#include <iostream>


using namespace std;


int main() {
  
  int a[10];
  
  for (int i=0; i<10;i++){
      a[i]=rand()%10;
      cout << a[i] << " ";
   }
   cout << endl;
     
   for (int i = 2; i < 10; i++){ 
           if (a[i] % i != 0) { 
               cout << a[i] << " ";  
           }
   }
  
    return 0;
}

[salem c]

rand() gives you random numbers, not prime numbers.

There's nothing in your code which suggests a primality test.

[Handy Andy]

Hello geovoulg,

To start with you need the header files "<cstdlib>" for "rand()" and "srand" and "<ctime>" for use with "srand". Since you do not seed the PRNG it will always produce the same numbers for your array.

Put this at the beginning of "main": srand(static_cast<unsigned int>(time(nullptr)));. It will help, but with such a short range you will still produce the same numbers, but maybe in a slightly different order.

Your second for loop only tests if the number in the array is even or odd not if it is a prime number. This needs fixed.

Since the code for checking for a prime number is not something I use very often, like me you will need to do a little research. Or wait awhile and someone will give you thee code that you need.

Andy

[gevCplus]

Ok guys! Thanks a lot for your replies! :)

[seeplus]

Your test for being prime is wrong. A number is prime if it has no divisors other than 1 and itself. All even numbers are not prime. Apart from 2, all primes are odd. Without special algorithms, you need to test a number for possible divisors and a number if only prime if none are found.

For a simple way, consider:

#include <random>
#include <iostream>
#include <cmath>

bool isPrime(unsigned long long no)
{
	if (no < 3)
		return no / 2;

	if (no % 2 == 0)
		return false;

	for (unsigned long long d = 3, l = sqrt(no); d <= l; d += 2)
		if (no % d == 0)
			return false;

	return true;
}

int main()
{
	const size_t many {10};
	const size_t maxn {10};

	std::mt19937 rng(std::random_device {}());
	std::uniform_int_distribution<size_t> distrib(1, maxn);

	for (size_t i = 0; i < many; ++i) {
		const auto rno {distrib(rng)};

		std::cout << rno << " is ";

		if (!isPrime(rno))
			std::cout << "not ";

		std::cout << "prime\n";
	}
}

[dutch]

It's easy to skip values divisible by 3 as well, speeding it up by another 30% or so.

bool isPrime(unsigned long long n)
{
    if (n < 4) return n > 1;
    if ((n % 2) * (n % 3) == 0) return false;
    for (unsigned long long d = 5, l = std::sqrt(n); d <= l; d += 6)
        if ((n % d) * (n % (d + 2)) == 0) return false;
    return true;
}

You can skip values divisible by 5, too, but it starts to get a little ridiculous.

bool isPrime(unsigned long long n)
{
    if (n < 6) return (n != 2) * (n != 3) * (n != 5) == 0;
    if ((n % 2) * (n % 3) * (n % 5) == 0) return false;
    for (unsigned long long d = 7, l = std::sqrt(n); d <= l; d += 30)
        if ((n %  d)
          * (n % (d +  4))
          * (n % (d +  6))
          * (n % (d + 10))
          * (n % (d + 12))
          * (n % (d + 16))
          * (n % (d + 22))
          * (n % (d + 24)) == 0)
            return false;
	return true;
}

[jonnin]

if you are checking for small values (I see a %10 in there!) you can get a list of primes online and make a lookup table:
vector<bool> isprime{0,1,1,1,0,1,0,1,0,0,0,1}; //go as far as you need, 0 thru 11 here
...
if(isprime[value])
cout << value;

this will work up to a million or so easily (you would probably write a side-program to generate the code to make the lookup table for that!) but at some point it gets 'too big' and you would need to start using primality tests. You can test primality with a very high probability without actually finding all the primes or factoring the numbers, you can look those up online they are straightforward.

for VERY small values you can use the gcd of N! to check it (gcd is built into c++). You can do a few more numbers in a 64 bit int by only multiply all the primes not a true factorial, and that works too. eg 1*2*3*5*7*11*13*17...
it stops working when your multiply overflows the integer, I forget how far out that is.