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

3 Asked on December 23, 2021

1 Asked on December 23, 2021

0 Asked on December 23, 2021 by ppspp

elementary number theory number theory sequences and series totient function

0 Asked on December 23, 2021

0 Asked on December 23, 2021

1 Asked on December 23, 2021

1 Asked on December 23, 2021

0 Asked on December 23, 2021

2 Asked on December 21, 2021 by aqee

1 Asked on December 21, 2021 by jay-lemmon

complex analysis complex integration definite integrals integration

4 Asked on December 21, 2021 by juan-esaul-gonzlez-rangel

3 Asked on December 21, 2021 by wz-s

0 Asked on December 21, 2021

complex analysis complex numbers roots of unity solution verification

0 Asked on December 21, 2021

1 Asked on December 21, 2021

computer science logic natural deduction proof theory sequent calculus

0 Asked on December 21, 2021 by sebastian-bustos

1 Asked on December 21, 2021

1 Asked on December 21, 2021 by frightlin

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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