AnswerBun.com

Prime number checker formula

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?

2 Answers

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

Add your own answers!

Related Questions

The Optimal Toaster Problem

1  Asked on December 23, 2021

     

Ask a Question

Get help from others!

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP