C o a number n is a prime number, should not be judging 2 - (n - 1)? Why you just need to determine 2 - SQRT (n)?

CodePudding user response:

10
1 x 10=10
2 x 5=10
3 x3=9
5 x 2=10
10 x 1=10

CodePudding user response:

If 2 cannot be divided, but also try 4, 6, 8,... ?
If 3 cannot be divided, but also try 9, 15, 21,... ? And so on,
A number if there is one factor, then within it the square root of the number should have, or there will be no factors,
So there must be a factor is not greater than the square root of n,
So decide whether n is a prime, just try in addition to the square root of n, needn't to n - 1,

CodePudding user response:

Judge 2 ~ SQRT (n) between the number, because less cycles, reduced the time complexity,

You compare the two to SQRT (n) between the number and the number between 2 ~ n - 1, n, the greater the time complexity is lower

CodePudding user response:

Remove double counting

CodePudding user response:

I hope it can help you: https://blog.csdn.net/it_xiangqiang/category_10581430.html
I hope it can help you: https://blog.csdn.net/it_xiangqiang/category_10768339.html