# 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?

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, then $$alt p$$ or $$blt p$$, or else $$atimes b=nge p^2$$.

Answered by J. W. Tanner on January 7, 2022

## Related Questions

### Find the coefficient of $x^{24}$ in the binomial equation

3  Asked on December 23, 2021

### Where to choose the point of expansion for taylor series?

1  Asked on December 23, 2021

### How to check if $phi(n)$ is a perfect square?

0  Asked on December 23, 2021 by ppspp

### Find the generating function of $S_n$(Please check my idea)

0  Asked on December 23, 2021

### Could the “post-forcing continuum” be a new cardinality?

0  Asked on December 23, 2021

### Are these true for a martingale? $Eleft[ frac{X_{n+1}}{X_n} right] = 1, Eleft[ frac{X_{n+2}}{X_n} right] = 1$

1  Asked on December 23, 2021

### Linear programming: model to only pick 10% of the variables as non zero

1  Asked on December 23, 2021

### Solving vector differential equation

0  Asked on December 23, 2021

### The Optimal Toaster Problem

1  Asked on December 23, 2021

### What does the “$bigwedge$” symbol mean in “$bigwedge_{j=1,ldots,M,jneq i}Delta_i(x)>Delta_j(x)”$?

2  Asked on December 21, 2021 by aqee

### Find $f(t)$ such that $int_0^{2 pi} f(t + theta) ln(2 sin frac{t}{2}) dt = frac{e^{i theta}}{e^{-i theta} – a e^{i phi}}$

1  Asked on December 21, 2021 by jay-lemmon

### Proving $frac1{2pi} int_0^{2pi} frac{R^2-r^2}{R^2-2Rrcostheta+r^2} dtheta =1$ by integrating $frac{R+z}{z(R-z)}$ without residue theorem.

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

### What is the ordinary differential equation for double exponential summation?

3  Asked on December 21, 2021 by wz-s

### What is the value of $1 -omega^h + omega^{2h} -…+(-1)^{n-1} omega^{(n-1)h}$ when $omega$ is a root of unity?

0  Asked on December 21, 2021

### Why are the supremums of this linearly interpolated function equal?

0  Asked on December 21, 2021

### What is the definition of “a derivation of a sequent “?

1  Asked on December 21, 2021

### Cartan Differentiable calculus. Show $g(x,y)= frac{f(x)-f(y)}{x-y}$ is differentiable at $(x_{0},x_{0})$

0  Asked on December 21, 2021 by sebastian-bustos

### Proving a linear map is surjective

1  Asked on December 21, 2021

### Probability of Normal Distribution

1  Asked on December 21, 2021 by frightlin

### The resultant of two homogeneous polynomials is homogeneous

1  Asked on December 21, 2021