Not an expert, but the key thing is usually factoring, e.g. finding which prime numbers multiplied together make a certain composite number. The hard part is finding which are the right prime numbers (there are lots of prime numbers). Finding numbers that are prime,just generally,is a very quick operation already.