Factorisation in c++

general
1

how to factorise any prime number in c++ ??

2

Hello,

A prime number can’t be factored, because the prime numbers themselves are the “factors” that form all other numbers.

A very easy way to do it is to use a prime table that contains some small primes (say, less than 1 million, for example), and using that table along with trial division you can factor any integer into its prime factors, provided that they are all less than 1 million.

An example code in C++ could be:

bool isprime(int N)
{
	if(N==2 or N == 3)
		return true;
    else
    {
		int lim = floor(sqrt(N))+1;
		for(int i = 2; i <= lim; i++)
		{
			if(N%i==0)
				return false;
		}
		return true;
    }
}
     
static vector<int> primes;
     
void primes_gen()
{
    vector<int> vec;
    for(int i = 2; i <= 10000; i++)
    {
		if(isprime(i)==true)
			primes.push_back(i);
    }
}
     
vector<int> trial_division(int n)
{
    vector<int> prime_factors;
    for(int i = 0; i < primes.size(); i++)
    {
		if(primes[i]*primes[i] > n)
		{
			break;
		}
		while(n % primes[i] == 0)
		{
			prime_factors.push_back(primes[i]);
			n = n/primes[i];
		}
    }
    if(n > 1)
		prime_factors.push_back(n);
    return prime_factors;
}

Note that there might be other ways, but this one is quite simple and it works relatively well!

Best regards,

Bruno

3

A prime number p can be factored in O(1), just output 1 and the number itself. :smiley:

2 Likes
4

a prime number…or any number into prime numbers???