tabacco
My RSS Feeds
Prime Numbers: What Are They & Who Cares? ET, That's Who!
posted Saturday, 8 July 2006
Prime Numbers:
What Are They & Who Cares?
ET, That’s Who!
Tabacco: In the Jodie Foster film “Contact”, the Extraterrestrials identify themselves as intelligent beings, and not space noise, by sending Prime Numbers as a signal. 1 beat - Pause, 2 beats – Pause, 3 beats – Pause, 5 beats – Pause, 7 beats – Pause, 11 beats – Pause, 13 beats – Pause, 17 beats – Pause, 19 beats – Pause, 23 beats – Pause, etc. etc. up to about 97. By doing this, there could be no possibility that the beats were random or natural. If you ever hear a series of beats in Prime Sequence, look up SETI’s (Search for Extra Terrestrial Intelligence) phone number and tell them you have made Contact with ET.
Integer:
An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For example, the prime divisors of 10 are 2 and 5; and the first six primes are 2, 3, 5, 7, 11 and 13. (The first 10,000, and other lists are available). The Fundamental Theorem of Arithmetic shows that the primes are the building blocks of the positive integers: every positive integer is a product of prime numbers in one and only one way, except for the order of the factors. (This is the key to their importance: the prime factors of an integer determine its properties.)
http://primes.utm.edu/largest.html#intro
Prime number
From Wikipedia, the free encyclopedia
In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. There exists an infinitude of prime numbers, as demonstrated by Euclid in about 300 B.C.. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113 (sequence A000040 in OEIS); see the list of prime numbers for a longer list.
The property of being a prime is called primality. Since 2 is the only even prime number, the term odd prime refers to all prime numbers greater than 2.
The study of prime numbers is part of number theory, the branch of mathematics, which encompasses the study of natural numbers. Prime numbers have been the subject of intense research, yet some fundamental questions remain such as the Riemann hypothesis or the Goldbach conjecture, which have been open for more than a century. The problem of modeling the distribution of prime numbers is a popular subject of investigation for number theorists: When looking at individual numbers, the primes seem to be randomly distributed, but the "global" distribution of primes follows well-defined laws.
The notion of prime number has been generalized in many different branches of mathematics. In the context of ring theory, a branch of abstract algebra, the term "prime element" has a specific meaning. Here, a ring element a is defined to be prime if whenever a divides b c for ring elements b and c, then a divides at least one of b or c. With this meaning, the additive inverse of any prime number is also prime. In other words, when considering the set of integers Z as a ring, - 7 is a prime element. Without further specification, however, "prime number" always means a positive integer prime. Among rings of complex algebraic integers, Eisenstein primes and Gaussian primes may also be of interest.
Prime divisors
The fundamental theorem of arithmetic states that every positive integer larger than 1 can be written as a product of primes in a unique way, i.e. unique except for the order. Primes are thus the "basic building blocks" of the natural numbers. For example, we can write
and any other factorization of 23244 as the product of primes will be identical except for the order of the factors. See prime factorization algorithm for details for how to do this in practice for larger numbers.
The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications.
Finding prime numbers
The Sieve of Eratosthenes is a simple way, and the Sieve of Atkin a fast way, to compute the list of all prime numbers up to a given limit.
In practice, though, one usually wants to check whether a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". Some of these tests are not perfect: there may be some composite numbers, called pseudoprimes for the respective test, that will be declared "probably prime" no matter what witness is chosen. However, the most popular probabilistic tests do not suffer from this drawback.
One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotients exceed the divisors, one can stop. This is known as trial division; it is the simplest primality test and it quickly becomes impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number-to-be-tested increases.
http://en.wikipedia.org/wiki/Prime_number
The most efficient way to find all of the small primes (say all those less than 10,000,000) is by using the Sieve of Eratosthenes (ca 240 BC):
Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.
For example, to find all the primes less than or equal to 30, first list the numbers from 2 to 30.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The first number 2 is prime, so keep it (we will color it green) and cross out its multiples (we will color them red), so the red numbers are not prime.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples. We know that all multiples less than 9 (i.e. 6) will already have been crossed out, so we can start crossing out at 32=9.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Now the first number left (still black) is 5, the second odd prime. So keep it also and cross out all of its multiples (all multiples less than 52=25 have already been crossed out, and in fact 25 is the only multiple not yet crossed out).
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The next number left, 7, is larger than the square root of 30, so there are no multiples of 7 to cross off that haven't already been crossed off (14 and 28 by 2, and 21 by 3), and therefore the sieve is complete. Therefore all of the numbers left are primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Notice we just found these primes without dividing.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
If you have given up the idea of becoming the 2nd Albert Einstein, and you still want to know whether a number is Prime or not without going through “Sieves”, go to the Primality Test @
http://primes.utm.edu/curios/includes/file.php?file=primetest.html
Simply type in the number in question, and quick as a wink the Primality gives you a “Yes” or “No” or answer.
Of course all even integers > 2 are automatically excluded as are all integers ending in 5; you already know they are not Primes.
Tabacco: all even integers greater than 2 are always divisible by 2. Therefore the number 2 is the only “Even Prime Number”. Below is Tabacco’s own little Chart for all integers up to 105 + a few more Primes up to and including 139. After that, you are on your own.
1 = 1 51 = 3x17 101 = 101
2 = 2 52 = 2x2x13 = 22x13 102 = 2x3x17
3 = 3 53 = 53 103 = 103
4 = 2x2 = 22 54 = 2x3x3x3 = 2x33 104 = 2x2x2x13 = 23x13
5 = 5 55 = 5x11 105 = 3x5x7
6 = 2x3 56 = 2x2x2x7 = 23x7
7 = 7 57 = 3x19 107 = 107
8 = 2x2x2 = 23 58 = 2x29
9 = 3x3 = 32 59 = 59 109 =109
10 = 2x5 60 = 2x2x3x5 = 22x3x5
11 = 11 61 = 61
12 = 2x2x3 = 22x3 62 = 2x31
13 = 13 63 = 3x3x7 = 32x7 113 = 113
14 = 2x7 64 = 2x2x2x2x2x2 = 26
15 = 3x5 65 = 5x13
16 = 2x2x2x2 = 24 66 = 2x3x11
17 = 17 67 = 67
18 = 2x3x3 = 2x32 68 = 2x2x17 = 22x17
19 = 19 69 = 3x23
20 = 2x2x5 = 22x5 70 = 2x5x7
21 = 3x7 71 = 71
22 = 2x11 72 = 2x2x2x3x3 = 23x32
23 = 23 73 = 73
24 = 2x2x2x3 = 23x3 74 = 2x37
25 = 5x5 = 52 75 = 3x5x5 = 3x55
26 = 2x13 76 = 2x2x19 = 22x19
27 = 3x3x3 = 33 77 = 7x11 127 = 127
28 = 2x2x7 = 22x7 78 = 2x3x13
29 = 29 79 = 79
30 = 2x3x5 80 = 2x2x2x2x5 = 24x5
31 = 31 81 = 3x3x3x3 = 34 131 = 131
32 = 2x2x2x2x2 = 25 82 = 2x41
33 = 3x11 83 = 83
34 = 2x17 84 = 2x2x3x7 = 22x3x7
35 = 5x7 85 = 5x17
36 = 2x2x3x3= 22x32 86 = 2x43
37 = 37 87 = 3x29 137 = 137
38 = 2x19 88 = 2x2x2x11 = 23x11
39 = 3x13 89 = 89 139 = 139
40 = 2x2x2x5 = 23x5 90 = 2x3x3x5 = 2x32x5
41 = 41 91 = 7x13
42 = 2x3x7 92 = 2x2x23 = 22x23
43 = 43 93 = 3x31
44 = 2x2x11 = 22x11 94 = 2x47
45 = 3x3x5 = 32x5 95 = 5x19
46 = 2x23 96 = 2x2x2x2x2x3 = 25x3
47 = 47 97 = 97
48=2x2x2x2x3= 24x3 98 = 2x7x7 = 2x72
49 = 7x7 = 72 99 = 3x3x11 = 32x11 149 = 149
50 = 2x5x5 = 2x52 100 = 2x2x5x5 = 22x52
In 1981's 'Body Heat', Kathleen Turner said, "Knowledge is power".
T.A.B.A.C.C.O. (Truth About Business And Congressional Crimes Organization)
What Are They & Who Cares?
ET, That’s Who!
Tabacco: In the Jodie Foster film “Contact”, the Extraterrestrials identify themselves as intelligent beings, and not space noise, by sending Prime Numbers as a signal. 1 beat - Pause, 2 beats – Pause, 3 beats – Pause, 5 beats – Pause, 7 beats – Pause, 11 beats – Pause, 13 beats – Pause, 17 beats – Pause, 19 beats – Pause, 23 beats – Pause, etc. etc. up to about 97. By doing this, there could be no possibility that the beats were random or natural. If you ever hear a series of beats in Prime Sequence, look up SETI’s (Search for Extra Terrestrial Intelligence) phone number and tell them you have made Contact with ET.
Integer:
An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For example, the prime divisors of 10 are 2 and 5; and the first six primes are 2, 3, 5, 7, 11 and 13. (The first 10,000, and other lists are available). The Fundamental Theorem of Arithmetic shows that the primes are the building blocks of the positive integers: every positive integer is a product of prime numbers in one and only one way, except for the order of the factors. (This is the key to their importance: the prime factors of an integer determine its properties.)
http://primes.utm.edu/largest.html#intro
Prime number
From Wikipedia, the free encyclopedia
In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. There exists an infinitude of prime numbers, as demonstrated by Euclid in about 300 B.C.. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113 (sequence A000040 in OEIS); see the list of prime numbers for a longer list.
The property of being a prime is called primality. Since 2 is the only even prime number, the term odd prime refers to all prime numbers greater than 2.
The study of prime numbers is part of number theory, the branch of mathematics, which encompasses the study of natural numbers. Prime numbers have been the subject of intense research, yet some fundamental questions remain such as the Riemann hypothesis or the Goldbach conjecture, which have been open for more than a century. The problem of modeling the distribution of prime numbers is a popular subject of investigation for number theorists: When looking at individual numbers, the primes seem to be randomly distributed, but the "global" distribution of primes follows well-defined laws.
The notion of prime number has been generalized in many different branches of mathematics. In the context of ring theory, a branch of abstract algebra, the term "prime element" has a specific meaning. Here, a ring element a is defined to be prime if whenever a divides b c for ring elements b and c, then a divides at least one of b or c. With this meaning, the additive inverse of any prime number is also prime. In other words, when considering the set of integers Z as a ring, - 7 is a prime element. Without further specification, however, "prime number" always means a positive integer prime. Among rings of complex algebraic integers, Eisenstein primes and Gaussian primes may also be of interest.
Prime divisors
The fundamental theorem of arithmetic states that every positive integer larger than 1 can be written as a product of primes in a unique way, i.e. unique except for the order. Primes are thus the "basic building blocks" of the natural numbers. For example, we can write
23244 = 22 X 3 X 13 X 149
and any other factorization of 23244 as the product of primes will be identical except for the order of the factors. See prime factorization algorithm for details for how to do this in practice for larger numbers.
The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications.
Finding prime numbers
The Sieve of Eratosthenes is a simple way, and the Sieve of Atkin a fast way, to compute the list of all prime numbers up to a given limit.
In practice, though, one usually wants to check whether a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". Some of these tests are not perfect: there may be some composite numbers, called pseudoprimes for the respective test, that will be declared "probably prime" no matter what witness is chosen. However, the most popular probabilistic tests do not suffer from this drawback.
One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotients exceed the divisors, one can stop. This is known as trial division; it is the simplest primality test and it quickly becomes impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number-to-be-tested increases.
http://en.wikipedia.org/wiki/Prime_number
The most efficient way to find all of the small primes (say all those less than 10,000,000) is by using the Sieve of Eratosthenes (ca 240 BC):
Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.
For example, to find all the primes less than or equal to 30, first list the numbers from 2 to 30.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The first number 2 is prime, so keep it (we will color it green) and cross out its multiples (we will color them red), so the red numbers are not prime.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples. We know that all multiples less than 9 (i.e. 6) will already have been crossed out, so we can start crossing out at 32=9.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Now the first number left (still black) is 5, the second odd prime. So keep it also and cross out all of its multiples (all multiples less than 52=25 have already been crossed out, and in fact 25 is the only multiple not yet crossed out).
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
The next number left, 7, is larger than the square root of 30, so there are no multiples of 7 to cross off that haven't already been crossed off (14 and 28 by 2, and 21 by 3), and therefore the sieve is complete. Therefore all of the numbers left are primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Notice we just found these primes without dividing.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
If you have given up the idea of becoming the 2nd Albert Einstein, and you still want to know whether a number is Prime or not without going through “Sieves”, go to the Primality Test @
http://primes.utm.edu/curios/includes/file.php?file=primetest.html
Simply type in the number in question, and quick as a wink the Primality gives you a “Yes” or “No” or answer.
Of course all even integers > 2 are automatically excluded as are all integers ending in 5; you already know they are not Primes.
Tabacco: all even integers greater than 2 are always divisible by 2. Therefore the number 2 is the only “Even Prime Number”. Below is Tabacco’s own little Chart for all integers up to 105 + a few more Primes up to and including 139. After that, you are on your own.
Prime Numbers
1 = 1 51 = 3x17 101 = 101
2 = 2 52 = 2x2x13 = 22x13 102 = 2x3x17
3 = 3 53 = 53 103 = 103
4 = 2x2 = 22 54 = 2x3x3x3 = 2x33 104 = 2x2x2x13 = 23x13
5 = 5 55 = 5x11 105 = 3x5x7
6 = 2x3 56 = 2x2x2x7 = 23x7
7 = 7 57 = 3x19 107 = 107
8 = 2x2x2 = 23 58 = 2x29
9 = 3x3 = 32 59 = 59 109 =109
10 = 2x5 60 = 2x2x3x5 = 22x3x5
11 = 11 61 = 61
12 = 2x2x3 = 22x3 62 = 2x31
13 = 13 63 = 3x3x7 = 32x7 113 = 113
14 = 2x7 64 = 2x2x2x2x2x2 = 26
15 = 3x5 65 = 5x13
16 = 2x2x2x2 = 24 66 = 2x3x11
17 = 17 67 = 67
18 = 2x3x3 = 2x32 68 = 2x2x17 = 22x17
19 = 19 69 = 3x23
20 = 2x2x5 = 22x5 70 = 2x5x7
21 = 3x7 71 = 71
22 = 2x11 72 = 2x2x2x3x3 = 23x32
23 = 23 73 = 73
24 = 2x2x2x3 = 23x3 74 = 2x37
25 = 5x5 = 52 75 = 3x5x5 = 3x55
26 = 2x13 76 = 2x2x19 = 22x19
27 = 3x3x3 = 33 77 = 7x11 127 = 127
28 = 2x2x7 = 22x7 78 = 2x3x13
29 = 29 79 = 79
30 = 2x3x5 80 = 2x2x2x2x5 = 24x5
31 = 31 81 = 3x3x3x3 = 34 131 = 131
32 = 2x2x2x2x2 = 25 82 = 2x41
33 = 3x11 83 = 83
34 = 2x17 84 = 2x2x3x7 = 22x3x7
35 = 5x7 85 = 5x17
36 = 2x2x3x3= 22x32 86 = 2x43
37 = 37 87 = 3x29 137 = 137
38 = 2x19 88 = 2x2x2x11 = 23x11
39 = 3x13 89 = 89 139 = 139
40 = 2x2x2x5 = 23x5 90 = 2x3x3x5 = 2x32x5
41 = 41 91 = 7x13
42 = 2x3x7 92 = 2x2x23 = 22x23
43 = 43 93 = 3x31
44 = 2x2x11 = 22x11 94 = 2x47
45 = 3x3x5 = 32x5 95 = 5x19
46 = 2x23 96 = 2x2x2x2x2x3 = 25x3
47 = 47 97 = 97
48=2x2x2x2x3= 24x3 98 = 2x7x7 = 2x72
49 = 7x7 = 72 99 = 3x3x11 = 32x11 149 = 149
50 = 2x5x5 = 2x52 100 = 2x2x5x5 = 22x52
In 1981's 'Body Heat', Kathleen Turner said, "Knowledge is power".
T.A.B.A.C.C.O. (Truth About Business And Congressional Crimes Organization)
comments