Discovering Prime Numbers
Author
Stephen Wolfram
Title
Discovering Prime Numbers
Description
Make a multiplication table:
Category
Educational Materials
Keywords
URL
http://www.notebookarchive.org/2019-08-98zxlvs/
DOI
https://notebookarchive.org/2019-08-98zxlvs
Date Added
2019-08-20
Date Last Modified
2019-08-20
File Size
220.4 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
Discovering Prime Numbers
Discovering Prime Numbers
Make a multiplication table:
In[]:=
Table[a*b,{a,2,10},{b,2,10}]//Grid
Out[]=
4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |
6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | 30 |
8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 |
10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 | 60 |
14 | 21 | 28 | 35 | 42 | 49 | 56 | 63 | 70 |
16 | 24 | 32 | 40 | 48 | 56 | 64 | 72 | 80 |
18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 | 90 |
20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
Find all the numbers that occur in the table:
In[]:=
Union[Flatten[Table[a*b,{a,2,10},{b,2,10}]]]
Out[]=
{4,6,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36,40,42,45,48,49,50,54,56,60,63,64,70,72,80,81,90,100}
This is what Union does (finds all elements that appear anywhere):
In[]:=
Union[{1,3,4,5,7,3},{6,5,3,2}]
Out[]=
{1,2,3,4,5,6,7}
Intersection finds elements that occur in both lists:
In[]:=
Intersection[{1,3,4,5,7,3},{6,5,3,2}]
Out[]=
{3,5}
Complement find elements from the first list that don’t occur in the second one:
In[]:=
Complement[Range[20],{4,5}]
Out[]=
{1,2,3,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Find numbers from the first 100 don’t occur in the multiplication table:
In[]:=
Complement[Range[100],Union[Flatten[Table[a*b,{a,2,50},{b,2,50}]]]]
Out[]=
{1,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}
The number that don’t occur are the primes.
Here’s the 10th prime:
In[]:=
Prime[10]
Out[]=
29
A table of the first 50 primes:
In[]:=
Table[Prime[n],{n,50}]
Out[]=
{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,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229}
The millionth prime:
In[]:=
Prime[1000000]
Out[]=
15485863
The 10^10th prime:
In[]:=
Prime[10^10]
Out[]=
252097800623
Counting Primes
Counting Primes
The number of primes less than 100:
In[]:=
Length[Complement[Range[100],Union[Flatten[Table[a*b,{a,2,50},{b,2,50}]]]]]
Out[]=
26
PrimePi computes this (though doesn’t treat 1 as a prime):
In[]:=
PrimePi[100]
Out[]=
25
Because 1 isn’t a prime, PrimePi[2] is 1:
In[]:=
PrimePi[2]
Out[]=
1
Plot the number of primes less than a given number:
In[]:=
ListPlot[Table[Prime[n],{n,50}]]
Out[]=
A larger version:
In[]:=
ListPlot[Table[Prime[n],{n,1000}]]
Out[]=
[[ UNFINISHED ]]
[[ UNFINISHED ]]
In[]:=
ListPlot[Range[2,100,2]]
Out[]=
In[]:=
56
Out[]=
56
In[]:=
Divisors[56]
Out[]=
{1,2,4,7,8,14,28,56}
In[]:=
FactorInteger[56]
Out[]=
{{2,3},{7,1}}
In[]:=
2^3*7^1
Out[]=
56
In[]:=
FactorInteger[424]
Out[]=
{{2,3},{53,1}}
In[]:=
424/2
Out[]=
212
In[]:=
%/2
Out[]=
106
In[]:=
%/2
Out[]=
53
In[]:=
FactorInteger[23452353452]
Out[]=
{{2,2},{11,1},{8237,1},{64709,1}}
In[]:=
FactorInteger[23452354345345353452]
Out[]=
{{2,2},{1483,1},{562297,1},{7031039513,1}}
In[]:=
FactorInteger[235353453453453453543]
Out[]=
{{3,3},{19,1},{133473083,1},{3437237317,1}}
In[]:=
PrimeNu[424]
Out[]=
2
In[]:=
Table[PrimeNu[n],{n,100}]
Out[]=
{0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,2,1,2,1,2,1,3,1,1,2,2,2,2,1,2,2,2,1,3,1,2,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,3,1,2,2,1,2,3,1,2,2,3,1,2,1,2,2,2,2,3,1,2,1,2,1,3,2,2,2,2,1,3,2,2,2,2,2,2,1,2,2,2}
In[]:=
ListLinePlot[Table[PrimeOmega[n],{n,100}]]
Out[]=
In[]:=
FactorInteger[56]
Out[]=
{{2,3},{7,1}}
In[]:=
FactorInteger[97]
Out[]=
{{97,1}}
In[]:=
2*2*3
Out[]=
12
In[]:=
2^5
Out[]=
32
In[]:=
ListLinePlot[Table[PrimeOmega[n],{n,2050}],PlotRangeAll]
Out[]=
In[]:=
2^10
Out[]=
1024
In[]:=
2^9*3
Out[]=
1536
In[]:=
ListPlot[Table[PrimePi[n]/n,{n,1000}]]
Out[]=
In[]:=
ListPlot[Table[PrimePi[n]/n,{n,10000}]]
Out[]=
In[]:=
PrimePi[1000]
Out[]=
168
PrimePi[1000]
In[]:=
FactorInteger[3453453463463463456325]
Out[]=
{{5,2},{7,1},{17,1},{59,1},{19674994806799393,1}}
In[]:=
457*234
Out[]=
106938
In[]:=
567^2
Out[]=
321489
In[]:=
RandomInteger[10^9]^2
Out[]=
86943733501123984
In[]:=
Timing[RandomInteger[10^9]^2]
Out[]=
{0.000012,636750733017957376}
In[]:=
Timing[RandomInteger[10^20]^2]
Out[]=
{0.000026,772743240587790205441708518164051692816}
In[]:=
Timing[RandomInteger[10^10000]^2;]
Out[]=
{0.000308,Null}
45678
In[]:=
Prime[1000]
Out[]=
7919
In[]:=
Prime[1001]
Out[]=
7927
In[]:=
Prime[1000]*Prime[1001]
Out[]=
62773913
In[]:=
GenerateAsymmetricKeyPair[]
Out[]=
PrivateKeyPrivateKey
,PublicKeyPublicKey
 |  |
|
|  |
|
Cite this as: Stephen Wolfram, "Discovering Prime Numbers" from the Notebook Archive (2019), https://notebookarchive.org/2019-08-98zxlvs
Download
