I'm doing an assignment which command me to count the numbers of future numbers in q elements given. A future number is a number which has all the divisors of it (1 and itself are not include) that are prime numbers. It doesn't print anything at all. Anyone have a suggestion why isn't it working ?!!

Sample input : 9

9 7 10 6 17 4 19 21 13

Sample output : 5

my code :

#include<bits/stdc  .h>
using std::cin;
using std::cout;
int i,j,count1=0,count_divisors;
int a[10005];
int prime_numbers(int n) {
    if(n<2) return 0;
    if(n==2||n==3) return 1;
    for(i=2;i<=sqrt(n);i  ) 
        if(n%i==0) return 0;
    return 1;
}
int main() {
    int q;
    cin>>q;
    for(i=0;i<q;i  ) cin>>a[i];
    for(i=0;i<q;i  ) {
        count_divisors=0;
        for(j=2;j<=sqrt(a[i]);j  ) {
            if(!(a[i]%j)) {
                int the=a[i]/j;
                if(prime_numbers(j)==0) break;
                if(prime_numbers(the)==0) break;
                count_divisors =2;
            }
            if(j>sqrt(a[i])&&count_divisors!=0) count1  ;
        }
    }
    cout<<count1;   
}

CodePudding user response：

I think the assignment is to find all numbers in an array that

• a) have at least one divisor (other than 1 or the number itself) and
• b) all those divisors are prime numbers.

Some examples:

• 9 => devisor(s): [3]; 3 is a prime number, so "9" counts.
• 7 => devisor(s): [none]; so "7" does NOT count.
• 20 => devisor(s): [2, 5, 10]; 10 is a divisor but not a prime number, so "20" does NOT count.

In the given example 5 of the numbers fulfill the criteria, namely 9, 10, 6, 4 and 21. That's 5 numbers, therefore the answer is "5".

Here is the code that does that for you:

#include <iostream>

bool is_prime_numbers(int n) {

    if (n < 2) {
        return false;
    }

    for (int i = 2; i < n; i  )
    {
        if (n % i == 0) {
            return false;
        }
    }
        
    return true;
}

int main() {

    int cnt = 0;
    int arr[1000];

    int q;
    cin >> q;
    //q = 9;

    for (int i = 0; i < q; i  )
        cin >> arr[i];
    /*arr[0] = 9;
    arr[1] = 7;
    arr[2] = 10;
    arr[3] = 6;
    arr[4] = 17;
    arr[5] = 4;
    arr[6] = 19;
    arr[7] = 21;
    arr[8] = 20;*/

    for (int i = 0; i < q; i  ) {

        bool found_divisor_prime = false;
        bool found_divisor_other = false;
        
        int val = arr[i];
        for (int div = 2; div < val; div  ) {

            //can "val" be devided by "div"?
            if ((val % div) == 0) {
                
                //is "div" a prime number?
                if (is_prime_numbers(div))
                    found_divisor_prime = true;
                else
                    found_divisor_other = true;
            }
        }

        /* we only want to count numbers that:
        * a) have a divisor other than 1 or the number itself
        * b) all divisors are prime numbers
        */
        if (found_divisor_prime && !found_divisor_other)
            cnt  ;
    }

    std::cout << cnt;

    return 0;
}

CodePudding user response：

The first bug is as AudioDroid stated that the global variable i is being changed by two functions, namely main and prime_numbers. This can be fixed by defining a local variable let's say k and looping through with it:

int k;
for (k = 2; k <= sqrt(n); k  ) {
    if (n % k == 0) return 0;
}

The second bug is that you wrote

if (j > sqrt(a[i]) && count_divisors != 0) count1  ;

inside the inner for loop body and thus it will never be executed. It has to be taken out of there. Fix these two bugs and you will get your 5 as an answer.

However in case you have q as big as let's say 10^6 or more this solution of yours will not be very effective because for every divisor d you are looping through the range [2; sqrt(d)] instead of generating all prime numbers up to a given limit in a lookup object and just checking whether the particular divisor is a prime number or not in O(1) time.

#include <memory>
#include <bitset>
#include <iostream>
#include <vector>

int const lim = 1000000;

bool is_future(int const num, std::unique_ptr<std::bitset<lim   1>> const& is_prime) {
    int div, cnt = 0;
    for (div = 2; div * div <= num;   div) {
        if (num % div == 0) {
              cnt;
            if (!is_prime->test(div)) {
                return false;
            }
            if (div * div != num) {
                  cnt;
                if (!is_prime->test(num / div)) {
                    return false;
                }
            }
        }
    }
    return cnt != 0;
}

int main() {
    auto sieve = std::make_unique<std::bitset<lim   1>>();
    sieve->set();
    sieve->set(0, false);
    sieve->set(1, false);
    int i, j;
    for (i = 2; i * i <= lim;   i) {
        if (sieve->test(i)) {
            for (j = i * i; j <= lim; j  = i) {
                sieve->set(j, false);
            }
        }
    }
    int q;
    std::cin >> q;
    std::vector<int> seq;
    seq.reserve(q);
    int k, num;
    for (k = 0; k != q;   k) {
        std::cin >> num;
        seq.emplace_back(num);
    }
    int ans = 0;
    for (auto const& elem : seq) {
        if (is_future(elem, sieve)) {
              ans;
        }
    }
    std::cout << ans << '\n';
    return 0;
}

Set your lim constant to be high enough according to the maximum value of the number in the input. Allocate bitset on the heap via the unique_ptr sieve. Run the sieve of Eratosthenes algorithm on sieve up to lim. Read q. Define the vector seq. Use reserve to allocate memory for q elements and thus avoid preallocation. Grow seq. Initialize the counter ans with 0. Loop through seq and for every element elem call is_future with elem and sieve. is_future uses is_prime (sieve) as a lookup object to check whether the divisor div or (num/div) is prime or not in O(1) time. The counter cnt counts the number of divisors of num in the range [2; sqrt(num)]. Pay attention that I don't use std::sqrt because it is expensive If called thousands of times. If cnt is 0 the number has no divisors in the specified range so it is not future otherwise it is. If is_future returns true increment ans. Output ans.