# Factorisation in c++

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

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

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

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

2 Likes
//