prime factorization.?

Question

what are the prime factors of 3741. is there an easier way to factorize big numbers?

Answer 1

No matter how big the number, you would start by testing for small factors (there is a formula for where it is good to stop this).

3741 = 3 * 1247

When the number has no small factors, "Fermat's method" of factoring it is to look at its difference from larger exact squares. 1247 is bigger than 35^2, so let's see:

1247 = 36^2 - 49 = 36^2 - 7^2 = (36 - 7)(36 + 7) = 29 * 43

If 36^2 hadn't worked, we could have gone on to try 37, 38 etcetera. There are tricks for not trying every square number.

There are pages everywhere on the web about methods of factorizing big numbers, ranging from the childish to the world-class research. The one below is maybe somewhere in the middle.

Answer 2

Many of the primes have easy ways to figure out:

2: A number is divisible by two if the last digit is 0, 2, 4, 6, 0r 8

3: If you add the digits up and the sum is divisible by 3, the whole number is also divisible by three. (3+4+7+4+1=15, so 3741 is also divisible by 3)

5: If the final number is 0 or 5

7: There is a trick, i just forgot it.

11: Take the last digit, subtract the second, add the third, subtract the fourth, ect. If the ending answer is divisible by 11 (Remember, 0 is divisible by 11!), so is your number (1-4+7-3)=1, so the number isnt divisible by 11.

Also, when checking from primes you only have to check up to the largest prime less than the square root of the number. So, in this case the largest prime you need to check is less than sqrt(3741)=61.1637

Answer 3

I've found that the easiest way in finding prime factors is to start dividing the number with the smallest possible prime factor. Then do the same for the remaining composite factors:

Answer 4

= 3 x 1247
= 3 x 29 x 43
I used trial and error by trying prime nos. 3,5,7,11,13,17 and so on.