Find if integer x is prime

@see primality test

Level 1:

Check if all integers between 2 and x – 1 give non-zero remainder when divided into x.

Level 2:

Check if all integers between 2 and x/2 give non-zero remainder when divided into x.

Level 3:

Check if all integers between 2 and sqrt(x) give non-zero remainder when divided into x.

Level 4:

Check if number 2 and all odd integers between 3 and sqrt(x) give non-zero remainder when divided into x.

Level 5:

Check if number 2 and number 3 and some integers between 5 and sqrt(x) give non-zero remainder when divided into x. Only check numbers via the following pattern:

  • check if 5 and 7 give non-zero remainder when divided into x
  • check if 5+6 and 7+6 give non-zero remainder when divided into x
  • check if 5+2*6 and 7+2*6 give non-zero remainder when divided into x
  • check if 5+3*6 and 7+3*6 give non-zero remainder when divided into x
  • etc

Level 6:

Check if number 2 and number 3 and some integers between 5 and sqrt(x) give non-zero remainder when divided into x. Only check numbers via the following pattern:

  • check if 5 and 7 give non-zero remainder when divided into x
  • check if 5+6 and 7+6 give non-zero remainder when divided into x
  • check if 5+2*6 and 7+2*6 give non-zero remainder when divided into x
  • check if 5+3*6 and 7+3*6 give non-zero remainder when divided into x
  • etc

but skip integers that end with 5.

Level 7:

Use Elliptic curve primality tests or other unconditional probabilistic methods like Goldwasser–Kilian test or  Miller–Rabin test

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s