Mathematics Asked by Mondo Duke on January 7, 2022
First let $N = p^2$. I think that to show that any number less than $N$ is prime, you only have to check to show it has factors less than $p$. Is this valid/is there some broader framework why?
Well, a target number can be proved to be prime by determining only that there are no prime numbers, up to the square root of the target number, that are factors of the target number. And while a computational application can be developed that completely and efficiently adheres to that process it is still not the fastest computational process related to trial division.
A faster process related to trial division tests for factors of the target number, up to the square root of the target number, in a sequence of numbers that have factors of 2, 3, 5, and 7 removed. Of course the numbers of 2, 3, 5, and 7 must themselves be tested as factors of the target number.
For instance a sequence of numbers with factors of 2 removed is just the odd numbers. However the odd numbers represent a sequence of numbers with repeating increments of 2. Then there are similar patterns of sequences of numbers, with repeating increments, for sequences of numbers with factors of 3, 5, and 7 removed. It is just very easy and fast to increment a sequence of numbers when the sequence of numbers has repeating increments.
Well, here is the development of a structure that is used for prime test factoring:
2
3, 5, 7, 9, 11, 13, 15 ...
That's repeating increments of 2 (on the second line)
Remaining factors of 3 are spaced at counts of 3
2, 3
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 ...
That's increments of 2, 4 ... as repeating
Remaining factors of 5 are spaced at counts of 7, 3 ... as repeating
2, 3, 5
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49 ...
That's increments of 4, 2, 4, 2, 4, 6, 2, 6 ... as repeating
Remaining factors of 7 are spaced at counts of 12, 7, 4, 7, 4, 7, 12, 3 ... as repeating
2, 3, 5, 7
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 ...
That's increments of 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as repeating
Answered by S Spring on January 7, 2022
To show that a number $n< p^2$ is not prime, you have to check only that it has factors less than $p$.
That is because, if $atimes b=n<p^2$, then $alt p$ or $blt p$, or else $atimes b=nge p^2$.
Answered by J. W. Tanner on January 7, 2022
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP