Variants of Primes |
There huge variants of primes numbers are existed in mathamatics these are useful in different mathematical and physical fields.
Composite numbers:
A composite number is a positive integer greater than 1 that is not a prime number, i.e., it can be divided evenly by more numbers than 1 and itself. Examples of composite numbers are 4, 6, 8, 9, 10, 12, and so on.
Prime numbers: Natural numbers greater than 1 that are only divisible by 1 and themselves.
Means,
- They contains only two factors
- 1 is common factor for all the primes
- 1 is not neither prime nor composite
- 2 is only even prime exist.
.jpg)
.jpg)
Code:
def is_prime(num):
if num <= 1:
return False
for i in range(2, num):
if num % i == 0:
return False
return True
num = int(input("Enter a number: "))
if is_prime(num):
print(f"{num} is a prime number.")
else:
print(f"{num} is not a prime number.")
Variants in primes:
Below articulate the different primes and their programming approach using standard mathematical formulae and theory. And also provides code.
1.Irregular prime:
An irregular prime is a prime number that is greater than the average gap between consecutive primes.
Approach :
1.Check if the number is prime:
A number n is prime if it is only divisible by 1 and itself. To check this, divide n by all the numbers from 2 to the square root of n and if none of them evenly divide n, then n is prime.
Calculate (p-1)!:
Calculate the factorial of p-1.
2.Calculate (p-1)! + 1:
Add 1 to the result from step 2.
3.Check if (p-1)! + 1 is prime:
Repeat the procedure from step 1 to check if (p-1)! + 1 is prime.
If the number p is prime and (p-1)! + 1 is not prime, then the number p is an irregular prime.
Code:
import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def is_irregular_prime(p):
fact = math.factorial(p - 1)
return is_prime(p) and not is_prime(fact + 1)
2.Pseudoprime numbers:
A pseudoprime number is a composite number that appears to be prime when tested using certain prime tests, but is not actually prime.
A strong pseudoprime is a composite number that passes a more stringent set of tests, while a Carmichael number is a composite number that satisfies Fermat's Little Theorem for all integers greater than 2, making it a type of pseudoprime
Discuss some prime check tests.
Prime check tests:
preliminary tests that can be used to quickly determine if a number is composite (not prime) without having to perform a full primality test. These tests can greatly reduce the time and computational effort required to determine if a number is prime. Some of the most commonly used preliminary tests include:
1.Trial division: This test involves dividing the number by a set of small primes (often called trial divisors) and checking if any of them evenly divide the number. If the number is evenly divided by any of the trial divisors, it is composite.
2.Fermat's Little Theorem: This test involves raising 2 to the power of the number minus 1 and checking if the result is equal to 1 modulo the number. If it is, the number is likely prime, although there is a small chance that it is a strong pseudoprime.
3.Miller-Rabin test: This test is a more sophisticated version of Fermat's Little Theorem and is less likely to be fooled by strong pseudoprimes.
3.Sophie Germain primes:
A Sophie Germain prime is a prime number that is also a prime when multiplied by 2 and added to 1.
Approach:
A number n is prime if it is only divisible by 1 and itself. To check this, divide n by all the numbers from 2 to the square root of n and if none of them evenly divide n, then n is prime.
Calculate 2p + 1:
Multiply the number p by 2 and add 1 to the result.
Check if 2p + 1 is also prime:
Repeat the procedure from step 1 to check if 2p + 1 is also prime.
If the number p is prime and 2p + 1 is also prime, then the number p is a Sophie Germain prime.
Code:
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def is_sophie_germain_prime(p):
return is_prime(p) and is_prime(2*p + 1)
Ex: when a number p is a prime then 2p+1 also a prime then it is called SG prime.
5: 2 * 5 + 1 = 11 is prime.
11: 2 * 11 + 1 = 23 is prime.
17: 2 * 17 + 1 = 35 is prime.
41: 2 * 41 + 1 = 83 is prime.
131: 2 * 131 + 1 = 263 is prime.
4.Super prime:
A super prime is a prime number that is also a prime when concatenated with other prime numbers.
Approach:
Check if the number is prime:
A number n is prime if it is only divisible by 1 and itself. To check this, divide n by all the numbers from 2 to the square root of n and if none of them evenly divide n, then n is prime.
Reverse the number:
Convert the number to a string, reverse the string, and convert it back to an integer.
Check if the reversed number is also prime:
Repeat the procedure from step 1 to check if the reversed number is also prime.
If both the number and its reverse are prime, then the number is a super prime.
Code:
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def is_super_prime(n):
return is_prime(n) and is_prime(int(str(n)[::-1]))
NOTE:
2^82,589,933 − 1, discovered in 2018, is a prime number with 24,862,048 digits.
2^74,207,281 − 1, discovered in 2016, is a prime number with 22,338,618 digits.
2^57,885,161 − 1, discovered in 2013, is a prime number with 17,425,170 digits.
2^43,112,609 − 1, discovered in 2006, is a prime number with 12,978,189 digits.
5.Additive primes:
An additive prime is a prime number that remains prime when a certain digit is added to it.
Ex:
11: the sum of its digits is 2, which is prime.
101: the sum of its digits is 2, which is prime.
131: the sum of its digits is 4, which is prime.
Approach:
1.Check if the number is prime:
A number n is prime if it is only divisible by 1 and itself. To check this, divide n by all the numbers from 2 to the square root of n and if none of them evenly divide n, then n is prime.
2.Sum the digits of the number:
Convert the number to a string and sum its digits.
Check if the sum of the digits is also prime:
Repeat the procedure from step 1 to check if the 3.sum of the digits is also prime.
If both the number and the sum of its digits are prime, then the number is an additive prime.
Code:
def is_additive_prime(num):
digit_sum = sum(int(digit) for digit in str(num))
is_prime_sum = is_prime(digit_sum)
is_prime_num = is_prime(num)
return is_prime_sum and is_prime_num
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
6.Permutable primes:
A permutable prime is a prime number that remains prime when its digits are rearranged.
Here is code implementation
Approach:
1.Check if the number is prime. To do this, divide the number by all positive integers less than the number and greater than 1. If none of these integers evenly divide the number, then the number is prime.
2.If the number is not prime, return false.
Create a list of the digits of the number.
3.Rearrange the digits of the number to form a new number.
4.Check if the new number is prime. To do this, divide the new number by all positive integers less than the new number and greater than 1. If none of these integers evenly divide the new number, then the new number is prime.
If the new number is not prime, return false.
5.Repeat steps 4-6 for all possible rearrangements of the digits of the original number.
6.If all rearranged numbers are prime, return true.
7.This procedure will determine if a number is a permutable prime or not.
Code:
from itertools import permutations
def is_permutable_prime(num):
if not is_prime(num):
return False
perms = set(int("".join(p)) for pFrn permutations(str(num)))
return all(is_prime(p) for p in perms)
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
7.Twin primes:
two prime numbers that differ by 2, such as 3 and 5 or 11 and 13.
Approach:
1.Take a sequence of prime numbers and check one by one number
2.And any consecutive prime numbers difference is 2 then return both as tuple
Code:
def is_twin_prime(p1, p2):
if is_prime(p1) and is_prime(p2) and abs(p1 - p2) == 2:
return True
return False
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
8.Regular primes:
primes that are not Sophie Germain or Mersenne primes.
Approach:
There is no specific formula to check if a number is a regular prime, but there are several algorithms that can be used to determine if a number is prime or not, such as trial division, the Sieve of Eratosthenes, or probabilistic primality tests like the Miller-Rabin test.
CODE:
def is_regular_prime(num):
if not is_prime(num):
return False
sg = 2 * num + 1
return not is_prime(sg)
9.Proth prime:
a prime number of the form k × 2^n + 1, where k is an odd integer and n is a positive integer.
Approach:
Check if the number is of the form k * 2^n + 1, where k is an odd integer and n is a positive integer.
Check if the number is prime. You can use any primality testing algorithm, such as trial division, the Sieve of Eratosthenes, or probabilistic primality tests like the Miller-Rabin test.
Code:
def is_proth_prime(num):
if (num - 1) % 2 != 0:
return False
k = (num - 1) // 2
n = 0
while k % 2 == 0:
k //= 2
n += 1
return is_prime(k) and (2 ** n * k + 1) == num
10.Woodall prime:
a prime number of the form k × 2^n - 1, where k is a positive integer and n is a positive integer.
Approach:
Check if the number is of the form 2^n - 1.
Check if n is a prime number.
Code:
def is_woodall_prime(num):
n = int(math.log2(num + 1))
return is_prime(n) and (2 ** n - 1) == num
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
~Loal Docums
Comments
Post a Comment