How to reverse sieve for prime numbers?
"Douglas Lewit [email protected] [ocaml_beginners]" <[email protected]> Thu, 16 Feb 2017 01:59:09 -0600
| Newsgroups | gmane.comp.lang.ocaml.beginners |
|---|---|
| Message-ID | <CAM0XMJRj1rNncACP6w-snXB03CUXNNuKYvyqk9xmnLyPOX0UgQ@mail.gmail.com> |
--94eb2c124ff40f42ef0548a12cdb
Content-Type: text/plain; charset=UTF-8
Hi everyone,
This is a function I created to filter out all the prime numbers from 2 to
some integer n. I like the function and it appears to be very fast and
efficient.
*let sieve num = let rec sequence lower upper = if lower > upper then [ ]
else lower :: sequence ( lower + 1 ) upper in *
* let integers = sequence 2 num in *
* let num' = float_of_int num in *
* let num'' = sqrt num' in *
* let num''' = ceil num'' in *
* let num'''' = int_of_float num''' in *
* let rec sieve' start potential_primes = *
* if start > num'''' then potential_primes *
* else sieve' ( start + 1 ) ( List.filter (
fun x -> if x > start && x mod start = 0 then false else true ) *
* potential_primes ) in *
* sieve' 2 integers ;;*
However, I'm having trouble with the reverse question. I know from
experimentation that there are 25 prime integers in the interval [2, 100).
That's great. I can find those integers by apply the function above
with *sieve
100*. But what a function called *findNPrimes 25* that returns the first
25 prime numbers? I'm finding that function rather difficult to write.
Any clues or hints? Thanks!!!
Best,
Douglas.
P.S. Does anyone know of any CS professors or professionals in the Chicago
area who are fairly adept at OCaml? Also, I am curious about something. I
read that OCaml really descended from a programming language called
STANDARD ML. How different is OCaml from Standard ML. Pretty close? Or
very different? I appreciate the feedback.
--94eb2c124ff40f42ef0548a12cdb
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/htm=
l4/strict.dtd">
<html>
<head>
</head>
=20
<body style=3D"background-color: #fff;">
<span style=3D"display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id=3D"ygrp-mlmsg" style=3D"position:relative;">
<div id=3D"ygrp-msg" style=3D"z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id=3D"ygrp-text" >
=20=20=20=20=20=20
=20=20=20=20=20=20
<p><div dir=3D"ltr"><font size=3D"4">Hi everyone,</font><div><font si=
ze=3D"4"><br></font></div><div><font size=3D"4">This is a function I create=
d to filter out all the prime numbers from 2 to some integer n.=C2=A0 I lik=
e the function and it appears to be very fast and efficient.</font></div><d=
iv><font size=3D"4"><br></font></div><div><font size=3D"4"><div><b><font co=
lor=3D"#4c1130">let sieve num =3D let rec sequence lower upper =3D if lower=
> upper then [ ] else lower :: sequence ( lower + 1 ) upper in=C2=A0</f=
ont></b></div><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0let in=
tegers =3D sequence 2 num in=C2=A0</font></b></div><div><b><font color=3D"#=
4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0let num' =3D float_of_int num in=C2=A0</=
font></b></div><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0let nu=
m'' =3D sqrt num' in=C2=A0</font></b></div><div><b><font color=
=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0let num''' =3D ceil num'=
' in=C2=A0</font></b></div><div><b><font color=3D"#4c1130">=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0let num'''' =3D int_of_float num'''=
; in=C2=A0</font></b></div><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0let rec sieve' start potential_primes =3D=C2=A0</font></b></d=
iv><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 i=
f start > num'''' then potential_primes=C2=A0</font></b>=
</div><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 else sieve' ( start + 1 ) ( List.filter ( fun x -> if x > sta=
rt && x mod start =3D 0 then false else true )=C2=A0</font></b></di=
v><div><b><font color=3D"#4c1130">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 pote=
ntial_primes ) in=C2=A0</font></b></div><div><b><font color=3D"#4c1130">=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 sieve' 2 integers ;;</font></b></div=
><div><b><font color=3D"#4c1130"><br></font></b></div><div><b><font color=
=3D"#4c1130"><br></font></b></div><div><font color=3D"#000000">However, I&#=
39;m having trouble with the reverse question.=C2=A0 I know from experiment=
ation that there are 25 prime integers in the interval [2, 100).=C2=A0 That=
's great.=C2=A0 I can find those integers by apply the function above w=
ith <b>sieve 100</b>.=C2=A0 But what a function called <b>findNPrimes 25</b=
> that returns the first 25 prime numbers?=C2=A0 I'm finding that funct=
ion rather difficult to write.=C2=A0 Any clues or hints?=C2=A0 Thanks!!!</f=
ont></div><div><font color=3D"#000000"><br></font></div><div><font color=3D=
"#000000">Best,</font></div><div><font color=3D"#000000"><br></font></div><=
div><font color=3D"#000000">Douglas.</font></div><div><font color=3D"#00000=
0"><br></font></div><div><font color=3D"#000000">P.S.=C2=A0 Does anyone kno=
w of any CS professors or professionals in the Chicago area who are fairly =
adept at OCaml?=C2=A0 Also, I am curious about something.=C2=A0 I read that=
OCaml really descended from a programming language called STANDARD ML.=C2=
=A0 How different is OCaml from Standard ML.=C2=A0 Pretty close?=C2=A0 Or v=
ery different?=C2=A0 I appreciate the feedback.</font></div><div><font colo=
r=3D"#000000"><br></font></div><div><font color=3D"#000000"><br></font></di=
v><div><font color=3D"#000000"><br></font></div><div><br></div></font></div=
></div>
</p>
</div>
=20=20=20=20=20
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style=3D"color: #fff; height: 0;">__._,_.___</div>
=20=20=20=20=20=20=20=20=20=20
=20=20
=20
=20=20=20=20
<div style=3D"clear:both"> </div>
<div id=3D"fromDMARC" style=3D"margin-top: 10px;">
<hr style=3D"height:2px ; border-width:0; color:#E3E3E3; background=
-color:#E3E3E3;">
Posted by: Douglas Lewit <[email protected]> <hr style=
=3D"height:2px ; border-width:0; color:#E3E3E3; background-color:#E3E3E3;">
</div>
<div style=3D"clear:both"> </div>
<table cellspacing=3D4px style=3D"margin-top: 10px; margin-bottom: 10px=
; color: #2D50FD;">
<tbody>
<tr>
<td style=3D"font-size: 12px; font-family: arial; font-weight: bo=
ld; padding: 7px 5px 5px;" >
<a style=3D"text-decoration: none; color: #2D50FD=
" href=3D"https://groups.yahoo.com/neo/groups/ocaml_beginners/conversations=
/messages/14769;_ylc=3DX3oDMTJxOWpuYmVwBF9TAzk3MzU5NzE0BGdycElkAzQ5OTkxOTQE=
Z3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzE0NzY5BHNlYwNmdHIEc2xrA3JwbHkEc3RpbWUDMTQ=
4NzIzMzU4NQ--?act=3Dreply&messageNum=3D14769">Reply via web post</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"mailto:[email protected]?subject=3DRe%3A%20How%20to%=
20reverse%20sieve%20for%20prime%20numbers%3F" style=3D"text-decoration: non=
e; color: #2D50FD;">
Reply to sender </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;">
<a href=3D"mailto:[email protected]?subject=3DRe%=
3A%20How%20to%20reverse%20sieve%20for%20prime%20numbers%3F" style=3D"text-d=
ecoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"https://groups.yahoo.com/neo/groups/ocaml_beginners/=
conversations/newtopic;_ylc=3DX3oDMTJlYjUyaWxkBF9TAzk3MzU5NzE0BGdycElkAzQ5O=
TkxOTQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTQ4NzIzMzU4=
NQ--" style=3D"text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;color: #2D50FD;" >
<a href=3D"https://groups.yahoo.com/neo/groups/=
ocaml_beginners/conversations/topics/14769;_ylc=3DX3oDMTM2c2c4bWIyBF9TAzk3M=
zU5NzE0BGdycElkAzQ5OTkxOTQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzE0NzY5BHNlYwNm=
dHIEc2xrA3Z0cGMEc3RpbWUDMTQ4NzIzMzU4NQR0cGNJZAMxNDc2OQ--" style=3D"text-dec=
oration: none; color: #2D50FD;">Messages in this topic</a>
(1)
</td>
</tr>
</tbody>
</table>
=20=20=20=20=20=20=20=20
<div id=3D"megaphoneModule">
<hr style=3D"height:2px ; border-width:0; color:#E3E3E3; backgr=
ound-color:#E3E3E3;">
<div>
<div class=3D"stream" style=3D"margin-bottom:10px;">
<div style=3D"background-color:white;">
<div class=3D"sn-img" style=3D"display:inline;"><img name=3D"tn=
_file" style=3D"padding:0px 10px;vertical-align:top;margin-top:5px;" src=3D=
"https://s.yimg.com/ru/static/images/yg/img/megaphone/1464031581_phpFA8bON"=
height=3D"82" width=3D"82"></div>
<div class=3D"mod-txt" style=3D"display:inline-block;">
<a rel=3D"nofollow" name=3D"sub_url" target=3D"_blank" href=
=3D"https://yho.com/1wwmgg" style=3D"color:#0000FF;display:block;margin-lef=
t:5px;text-decoration:none;"><span style=3D"font-size:15px;">Have you tried=
the highest rated email app?</span></a>
<div style=3D"max-width:530px;padding:2px 5px;">With 4.5 st=
ars in iTunes, the Yahoo Mail app is the highest rated email app on the mar=
ket. What are you waiting for? Now you can access all your inboxes (Gmail, =
Outlook, AOL and more) in one place. Never delete an email again with 1000G=
B of free cloud storage.</div>
</div>
</div>
</div> </div>=20=20
=20=20=20=20=20
<hr style=3D"height:2px ; border-width:0; color:#E3E3E3; background-col=
or:#E3E3E3;">
</div>
<!------- Start Nav Bar ------>
<div id=3D"ygrp-grfd" style=3D"font-family: Verdana; font-size: 12px; p=
adding: 15px 0;">
=20=20=20=20=20=20
<!-- |**|begin egp html banner|**| -->
Archives up to December 31, 2011 are also downloadable at <a href=3D"=
http://www.connettivo.net/cntprojects/ocaml_beginners">http://www.connettiv=
o.net/cntprojects/ocaml_beginners</a><BR>
The archives of the very official ocaml list (the seniors' one) can be foun=
d at <a href=3D"http://caml.inria.fr">http://caml.inria.fr</a><BR>
Attachments are banned and you're asked to be polite, avoid flames etc. =
=20=20
<!-- |**|end egp html banner|**| -->
</div>
=20=20
=20
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-vital" style=3D"background-color: #f2f2f2; font-family: Ver=
dana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-transf=
orm: uppercase; "><a href=3D"https://groups.yahoo.com/neo/groups/ocaml_begi=
nners/info;_ylc=3DX3oDMTJldDhhMWlyBF9TAzk3MzU5NzE0BGdycElkAzQ5OTkxOTQEZ3Jwc=
3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTQ4NzIzMzU4NQ--" style=
=3D"text-decoration: none;">Visit Your Group</a></span>
<ul style=3D"list-style-type: none; margin: 0; padding: 0; display: in=
line;">
</ul>
</div>
<div id=3D"ft" style=3D"font-family: Arial; font-size: 11px; margin-top: 5p=
x; padding: 0 2px 0 0; clear: both;">
<a href=3D"https://groups.yahoo.com/neo;_ylc=3DX3oDMTJkMGRrcmd2BF9TAzk3ND=
c2NTkwBGdycElkAzQ5OTkxOTQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzd=
GltZQMxNDg3MjMzNTg1" style=3D"float: left;"><img src=3D"http://l.yimg.com/r=
u/static/images/yg/img/email/new_logo/logo-groups-137x15.png" height=3D"15"=
width=3D"137" alt=3D"Yahoo! Groups" style=3D"border: 0;"/></a>
<div style=3D"color: #747575; float: right;"> • <a href=3D"https://i=
nfo.yahoo.com/privacy/us/yahoo/groups/details.html" style=3D"text-decoratio=
n: none;">Privacy</a> • <a href=3D"mailto:ocaml_beginners-unsubscribe@=
yahoogroups.com?subject=3DUnsubscribe" style=3D"text-decoration: none;">Uns=
ubscribe</a> • <a href=3D"https://info.yahoo.com/legal/us/yahoo/utos/t=
erms/" style=3D"text-decoration: none;">Terms of Use</a> </div>
</div>
<br>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
=20
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-sponsor" style=3D"width:160px; float:right; clear:none; m=
argin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id=3D"ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style=3D"clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src=3D"http://geo.yahoo.com/serv?s=3D97359714/grpId=3D4999194/grpspI=
d=3D1705006764/msgId=3D14769/stime=3D1487233585" width=3D"1" height=3D"1"> =
<br>
<img src=3D"http://y.analytics.yahoo.com/fpc.pl?ywarid=3D515FB27823A7407E&a=
=3D10001310322279&js=3Dno&resp=3Dimg&cf12=3DCP" width=3D"1" height=3D"1">=20
<div style=3D"color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type=3D"text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
=20=20
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.fi=
le-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div=
.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}=20
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;=20
}=20
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--94eb2c124ff40f42ef0548a12cdb--