creating dynamic array that sums prime numbers

[CollinsLainzo]

Hello guys,

I am having challenges with how I am suppose to go about coding the following problem:

An array is defined to be a Magic array if the sum of the primes in the array is equal to the first element of the array. If there are no primes in the array, the first element must be 0. So {21, 3, 7, 9, 11 4, 6} is a Magic array because 3, 7, 11 are the primes in the array and they sum to 21 which is the first element of the array. {13, 4, 4, 4, 4} is also a Magic array because the sum of the primes is 13 which is also the first element. Other Magic arrays are {10, 5, 5}, {0, 6, 8, 20} and {3}. {8, 5, -5, 5, 3} is not a Magic array because the sum of the primes is 5+5+3 = 13. Note that -5 is not a prime because prime numbers are positive.

Write a function named isMagicArray that returns 1 if its integer array argument is a Magic array. Otherwise it returns 0.

Any ideas will be welcome. Thanks! in advance

[salem c]

I guess you could start with

// return 1 if prime, 0 if composite
int isPrime(int numberToTest ) {
    int result = 1;  // assume prime
    // some code to falsify the assumption
    return result;
}

Use that to scan through your potential magic array, summing those which are prime.

[jugu]

bool is_prime(int number) {
	if (number < 1) return false;
	for (int divisor = number / 2; divisor > 1; --divisor)
		if (number % divisor == 0) return false;
	return true;
}

bool is_magic_array(std::vector<int> const & vect) {
	long sum = 0L;
	std::for_each(vect.begin(), vect.end(), [&sum](int number) { 
               if (is_prime(number)) sum += number; });
	return sum == vect[0];
}

[jugu]

To make sure you've got a valid array, add the following line before starting to accumulate the sum:
if (vect.size() == 0) return false;

[Browni3141]

Any solution will iterate through each element in the array, check for primarily and sum the primes. The best primality test depends on the context.

If the function will be called many times and the elements are not very large using a prime sieve to find all primes up to a given magnitude works best. Otherwise use a prime test. The simplest prime test is to test for divisibility by every potential prime up to and including the square root of the number you’re testing. If you are really lazy you can just check every number up to the root, if you’re a little lazy check 2 and every odd number, if you are not lazy check 2, 3 and every number of the form 6x+1 and 6x+5. There’s not much to gain from using more complex patterns.

One big optimization is to terminate the search as soon as the sum exceeds the target number.

If the array may potentially contain extremely large numbers (bigger than a 64 bit number) you may want to research stronger primality tests.