129 lines
10 KiB
HTML
129 lines
10 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<title>The Twin Primes Conjecture</title>
|
|
<link href="../docs-assets/Breadcrumbs.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<meta name="viewport" content="width=device-width initial-scale=1">
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
|
<meta http-equiv="Content-Language" content="en-gb">
|
|
|
|
<link href="../docs-assets/Contents.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<link href="../docs-assets/Progress.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<link href="../docs-assets/Navigation.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<link href="../docs-assets/Fonts.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<link href="../docs-assets/Base.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<script>
|
|
MathJax = {
|
|
tex: {
|
|
inlineMath: '$', '$'], ['\\(', '\\)'
|
|
},
|
|
svg: {
|
|
fontCache: 'global'
|
|
}
|
|
};
|
|
</script>
|
|
<script type="text/javascript" id="MathJax-script" async
|
|
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js">
|
|
</script>
|
|
|
|
<script>
|
|
function togglePopup(material_id) {
|
|
var popup = document.getElementById(material_id);
|
|
popup.classList.toggle("show");
|
|
}
|
|
</script>
|
|
|
|
<link href="../docs-assets/Popups.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
<link href="../docs-assets/Colours.css" rel="stylesheet" rev="stylesheet" type="text/css">
|
|
|
|
</head>
|
|
<body class="commentary-font">
|
|
<nav role="navigation">
|
|
<h1><a href="../index.html">
|
|
<img src="../docs-assets/Octagram.png" width=72 height=72">
|
|
</a></h1>
|
|
<ul><li><a href="../inweb/index.html">inweb</a></li>
|
|
</ul><h2>Foundation Module</h2><ul>
|
|
<li><a href="../foundation-module/index.html">foundation</a></li>
|
|
<li><a href="../foundation-test/index.html">foundation-test</a></li>
|
|
</ul><h2>Example Webs</h2><ul>
|
|
<li><a href="../goldbach/index.html">goldbach</a></li>
|
|
<li><span class="unlink">twinprimes</span></li>
|
|
<li><a href="../eastertide/index.html">eastertide</a></li>
|
|
</ul><h2>Repository</h2><ul>
|
|
<li><a href="https://github.com/ganelson/inweb"><img src="../docs-assets/github.png" height=18> github</a></li>
|
|
</ul><h2>Related Projects</h2><ul>
|
|
<li><a href="../../../inform/docs/index.html">inform</a></li>
|
|
<li><a href="../../../intest/docs/index.html">intest</a></li>
|
|
|
|
</ul>
|
|
</nav>
|
|
<main role="main">
|
|
<!--Weave of 'The Twin Primes Conjecture' generated by Inweb-->
|
|
<div class="breadcrumbs">
|
|
<ul class="crumbs"><li><a href="../index.html">Home</a></li><li><b>The Twin Primes Conjecture</b></li></ul></div>
|
|
<p class="purpose">This example of using inweb is a whole web in a single short file, to look for twin primes, a classic problem in number theory.</p>
|
|
|
|
<ul class="toc"><li><a href="S-all.html#SP1">§1. The conjecture</a></li><li><a href="S-all.html#SP2">§2. Primality</a></li></ul><hr class="tocbar">
|
|
|
|
<p class="commentary firstcommentary"><a id="SP1" class="paragraph-anchor"></a><b>§1. The conjecture. </b>It is widely believed that there are an infinite number of twin primes, that
|
|
is, prime numbers occurring in pairs different by 2. Twins are known to exist
|
|
at least as far out as \(10^{388,342}\) (as of 2016), and there are infinitely
|
|
many pairs of primes closer together than about 250 (Zhang, 2013; Tao, Maynard,
|
|
and many others, 2014).
|
|
</p>
|
|
|
|
<p class="commentary">This program finds a few small pairs of twins, by the simplest method possible,
|
|
and should print output like so:
|
|
</p>
|
|
|
|
<pre class="displayed-code all-displayed-code code-font">
|
|
<span class="plain-syntax"> 3 and 5</span>
|
|
<span class="plain-syntax"> 5 and 7</span>
|
|
<span class="plain-syntax"> 11 and 13</span>
|
|
<span class="plain-syntax"> ...</span>
|
|
</pre>
|
|
<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="constant-syntax">RANGE</span><span class="plain-syntax"> </span><span class="constant-syntax">100</span><span class="plain-syntax"> </span><span class="comment-syntax"> the upper limit to the numbers we will consider</span>
|
|
</pre>
|
|
<pre class="displayed-code all-displayed-code code-font">
|
|
<span class="plain-syntax">#</span><span class="identifier-syntax">include</span><span class="plain-syntax"> <</span><span class="identifier-syntax">stdio</span><span class="plain-syntax">.</span><span class="identifier-syntax">h</span><span class="plain-syntax">></span>
|
|
|
|
<span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="function-syntax">main</span><span class="plain-syntax">(</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">argc</span><span class="plain-syntax">, </span><span class="reserved-syntax">char</span><span class="plain-syntax"> *</span><span class="identifier-syntax">argv</span><span class="plain-syntax">[]) {</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax">=1; </span><span class="identifier-syntax">i</span><span class="plain-syntax"><</span><span class="constant-syntax">RANGE</span><span class="plain-syntax">; </span><span class="identifier-syntax">i</span><span class="plain-syntax">++)</span>
|
|
<span class="plain-syntax"> </span><span class="named-paragraph-container code-font"><a href="S-all.html#SP1_1" class="named-paragraph-link"><span class="named-paragraph">Test for twin prime at i</span><span class="named-paragraph-number">1.1</span></a></span><span class="plain-syntax">;</span>
|
|
<span class="plain-syntax">}</span>
|
|
</pre>
|
|
<p class="commentary firstcommentary"><a id="SP1_1" class="paragraph-anchor"></a><b>§1.1. </b><span class="named-paragraph-container code-font"><span class="named-paragraph-defn">Test for twin prime at i</span><span class="named-paragraph-number">1.1</span></span><span class="comment-syntax"> =</span>
|
|
</p>
|
|
|
|
<pre class="displayed-code all-displayed-code code-font">
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">if</span><span class="plain-syntax"> ((</span><a href="S-all.html#SP2" class="function-link"><span class="function-syntax">isprime</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">i</span><span class="plain-syntax">)) && (</span><a href="S-all.html#SP2" class="function-link"><span class="function-syntax">isprime</span></a><span class="plain-syntax">(</span><span class="identifier-syntax">i</span><span class="plain-syntax">+2)))</span>
|
|
<span class="plain-syntax"> </span><span class="identifier-syntax">printf</span><span class="plain-syntax">(</span><span class="string-syntax">"%d and %d\n"</span><span class="plain-syntax">, </span><span class="identifier-syntax">i</span><span class="plain-syntax">, </span><span class="identifier-syntax">i</span><span class="plain-syntax">+2);</span>
|
|
</pre>
|
|
<ul class="endnotetexts"><li>This code is used in <a href="S-all.html#SP1">§1</a>.</li></ul>
|
|
<p class="commentary firstcommentary"><a id="SP2" class="paragraph-anchor"></a><b>§2. Primality. </b>This simple and slow test tries to divide by every whole number at least
|
|
2 and up to the square root: if none divide exactly, the number is prime.
|
|
A common error with this algorithm is to check where \(m^2 < n\), rather
|
|
than \(m^2 \leq n\), thus wrongly considering 4, 9, 25, 49, ... as prime:
|
|
Cambridge folklore has it that this bug occurred on the first computation
|
|
of the EDSAC computer on 6 May 1949.
|
|
</p>
|
|
|
|
<pre class="definitions code-font"><span class="definition-keyword">define</span> <span class="constant-syntax">TRUE</span><span class="plain-syntax"> </span><span class="constant-syntax">1</span>
|
|
<span class="definition-keyword">define</span> <span class="constant-syntax">FALSE</span><span class="plain-syntax"> </span><span class="constant-syntax">0</span>
|
|
</pre>
|
|
<pre class="displayed-code all-displayed-code code-font">
|
|
<span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="function-syntax">isprime</span><button class="popup" onclick="togglePopup('usagePopup1')"><span class="comment-syntax">?</span><span class="popuptext" id="usagePopup1">Usage of <span class="code-font"><span class="function-syntax">isprime</span></span>:<br/><a href="S-all.html#SP1_1">§1.1</a></span></button><span class="plain-syntax">(</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">n</span><span class="plain-syntax">) {</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">n</span><span class="plain-syntax"> <= </span><span class="constant-syntax">1</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="constant-syntax">FALSE</span><span class="plain-syntax">;</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="reserved-syntax">int</span><span class="plain-syntax"> </span><span class="identifier-syntax">m</span><span class="plain-syntax"> = </span><span class="constant-syntax">2</span><span class="plain-syntax">; </span><span class="identifier-syntax">m</span><span class="plain-syntax">*</span><span class="identifier-syntax">m</span><span class="plain-syntax"> <= </span><span class="identifier-syntax">n</span><span class="plain-syntax">; </span><span class="identifier-syntax">m</span><span class="plain-syntax">++)</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">n</span><span class="plain-syntax"> % </span><span class="identifier-syntax">m</span><span class="plain-syntax"> == </span><span class="constant-syntax">0</span><span class="plain-syntax">)</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="constant-syntax">FALSE</span><span class="plain-syntax">;</span>
|
|
<span class="plain-syntax"> </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="constant-syntax">TRUE</span><span class="plain-syntax">;</span>
|
|
<span class="plain-syntax">}</span>
|
|
</pre>
|
|
<!--End of weave-->
|
|
|
|
</main>
|
|
</body>
|
|
</html>
|
|
|