Listing out prime dividers of numbers given

Viewed 113

I'm trying to solve a problem on one interactive website and after trying the code with some examples of mine it seems to work, however, if I load it on the website, it says there's a wrong answer which leads me to think that there is one (or multiple) cases where my code fails to execute correctly but I can't seem to find such.

The problem is:

For each given whole positive number return its prime divisors in ascending order. The first line of the input (a natural number) is how many numbers we want to check. In the following lines are numbers greater than 2. For each number return (in one line) that number, a semicolon and its prime divisors in ascending order. Each divisor has to appear only once.

Example:

 2
 12
 1024

Should return

12: 2 3
1024: 2

My C++ code:

#include <iostream>

using namespace std;

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

int main()
{
    int no_of_inputs;
    cin >> no_of_inputs;
    for (int i = 0; i < no_of_inputs; i++)
    {
        int val;
        cin >> val;
        cout << val<<": ";
        for (int i = 2; i < val; i++)
        {
            if (val% i == 0)
            {
                if (prime_check(i) == 1)
                {
                    cout << i<< " ";
                }
            }
        }
        cout << endl;
    }
}
1 Answers

I recommend to you that use the algorithm the Sieve of Eratosthenes for you selected all prime and assigned the prime divisores to each number in the range:

std::map<int, std::vector<int>> primeDiv;
bool noPrimes[MAXINTERGER] = {0};
void criba(){
    for(int i = 2; i <= MAXINTERGER; ++i)
        if(!noPrimes[i])
            for(int j = 2; i*j <= MAXINTERGER;j++){
                noPrimes[i*j] = true;
                primeDiv[i*j].push_back(i);
            }
}

and finally in your main the prime divisor for val are primeDiv[val], you can iterate and print the values. Be carefull with the presentation error!


Sieve of Eratosthenes algorithm on action

               Sieve of Eratosthenes algorithm

Related