# Find if integer x is prime

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