The sum of all non-prime odd numbers that precede an integer?

Question

Example 1 of execution:

Entrada ( numero inteiro): 10

Output: 10

So far I have it:

num =10;

for (i = 2; i < num ; i++)

   {

    if (num % i == 1 ){

        printf("%d\n", i);

        soma2 = i + soma2;


    }
}

But in the output appears: 3 and 9 and not only 9.

Answer 1

The simplest way to implement it is:

1. Read the number n;
2. Starts sum to zero;
3. Traverse the range [1, n] in k;
4. Checks if k is a prime number. If yes, it goes back to 3; if it does not continue;
5. Check if the number is odd. If not, go back to 3; if yes, continue;
6. Sum the value of k in sum;
7. Displays result;

But the solution doesn’t scale very well as the value of n grows. The function that checks if it is prime would have complexity O(n) and the implemented function would call such a function n times, which would result in a solution O(n²).

For a better scalable solution, you can check the problem from a mathematical point of view (because it’s a mathematical problem, right? ). Finding prime numbers in a closed interval is relatively simple when implementing the Eratosthenes sieve and calculating their sum will also be trivial. Thus, if you want the sum of all the nonprime odd numbers in the range, you simply compute the sum of all the odd numbers and subtract the sum of the prime numbers (don’t forget that 2 is prime, but it is even).

It is possible to demonstrate that the sum of all odd numbers in the range [1, n] is given by m², where m is the quantity of odd numbers in the range. If n is odd, m = (n+1)/2 and if n is even, m = n/2. Generally speaking, m = (n + n % 2)/2. Therefore, we know that the sum of all odd numbers will be ((n + n % 2)/2)², which is an operation O(1), does not depend on the dimension of n, always has the same number of operations.

After that, we can calculate the sum of the prime numbers in the range [1, n]:

• Sum of primes in a range in C

And to get the desired result, we sum all odd numbers by subtracting the sum of all odd numbers (and adding 2, which is prime but is not odd). Therefore, the algorithm would become:

1. Read the number n;
2. Computes the sum of all odd numbers in the range [1, n];
3. Computes the sum of all prime numbers in the range [1, n];
4. The sum of all non-prime odd is: sum_odd - summing up_cousins + 2;
5. Displays the result;

And this way you will have a much more scalable solution than the first alternative.

For n = 10, we would have:

• Sum of all odd: 25
• Sum of all cousins: 17
• Result: 25 - 17 + 2 = 10

Additional readings:

• How to generate 200,000 primes as fast as possible in Python?

Answer 2

Something like this:

num = 10;
soma = 0;

for(int i = 2; i < num; i++){ 
    if(!isEven(i) && !isPrime(i)){
        soma += soma;
    } 
} 

List of some prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

I don’t know what your performance goal is, but if you just need the algorithm to work with input limitation, you can use fixed data of prime numbers or the list of nonprime odd numbers. This way you would only have to loop through the numbers and filter through the values smaller than your input.

In the case of input 10 I would traverse the fixed data and find the odd nonprime integers 1 and 9, then add each of these and the result would be 10.

Another way would be to create numbers and check if they are non-prime numbers and are odd, if they are accumulating the value in a variable until it reaches its upper limit (input value).

Answer 3

You must implement the algorithm Sieve of Eratosthenes in your code, and save in an array the numbers that do not pass through the sieve.

After that you traverse the array with the numbers that did not pass through the sieve, adding up the values.

That’s it.