O'Reilly logo

Data Structures and Algorithms Using Java by William McAllister

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

APPENDIX C

Proof That If an Integer, P, Is Not Evenly Divisible by an Integer Less Than the Square Root of P, It Is a Prime Number

Preliminary Proof

Given:

R = the square root of P.

Prove:

If P = H * L, either H = L = the square root of P, or H or L is < R and the other is > R.

Proof:

If both were > R, then their product would be greater then P, and if both were less than R, their product would be less than P.

 

Desired Proof

Given:

There are no integers less than R (the square root of P) that divide evenly into P.

Prove:

There are no integers greater than R that divide evenly into P.

Proof:

Assume:H is an integer > R and that H divides evenly into.

Then: Define Las L = P / H.

L is an integer, since L = P / H and H divides evenly into P

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required