1. Primes
What am I supposed to do with all these prime numbers?
I've got buckets full already, and your programs are
making them faster and faster.
Is there any market for these?
Do I sell 'em by the pound, or by the dozen?
Irv
-------------------------------------------------
Visit my Euphoria programming web site:
http://www.mindspring.com/~mountains
-------------------------------------------------
2. Re: Primes
> What am I supposed to do with all these prime numbers?
> I've got buckets full already, and your programs are
> making them faster and faster.
>
> Is there any market for these?
> Do I sell 'em by the pound, or by the dozen?
>
> Irv
well first you have to make sure to sieve them, like you do with
noodles or spaghetti, otherwise they are runny.
--------------------------------------
If it wasn't for typos,
I'd never get any coding done at all.
;)
3. Re: Primes
>From: Arthur Adamson <euclid at isoc.net>
>Subject: Re: Primes
>X-Attachments: E:\0NEW\PRIMCMPR\HILLEY4.EX;
>Date: Mon, 9 Mar 1998 11:05:13 -0500
>
> I posted the following PRIME-FINDING times recently. Lucius Hilley
>volunteered numerous improvements in the sieve progs and his prog now is
>slightly faster than my version of the RDS sieve. Further he has found a way
>to use the sieve-flags-sequence as a place to also store the primes found,
>thus easing memory requirements and allowing larger values to be found.
> With Lucius' prog, see below, I can run a max prime of 10,000,000 in
>10.78 seconds whereas with the RDS version, I an limited to about 1,300,000
>before causeway errors take over. Lucius' prog quits gracefully for
>15,000,000 input with an out of memory message. I have 32 megs RAM.
I am running dos 6.21 and have often been plagued by causeway
crashes. My setup may not be optimum or typical in this regard.
> Viva La Difference
>
> I can now take a closer look at some of the other suggestions which
>have come in recently and which I have been neglecting while helping iterate
>Lucius' prog changes.
>>---------------------------------------
>>>>> From: Arthur Adamson <euclid at ISOC.NET>
>>>>> Date: Friday, March 06, 1998 10:44 PM
>>>> <SNIP>
>>>>> > For the first 100000 primes and a Pentium 120, I get times:
>>>>> > Seconds
>>>>> >Mike's prime.ex 38.77
>>>>> >Carl's oprime.ex 24.93
>>>>> >My mod apaprime.ex 21.83
>>>>> >Carl's sieve 2.73
>>>>> >RDSsieve 1.31
>>>>> >Chris 17.08
> Lucius' sieve 1.31 added Mar 9
>
>
>--primes.ex From Lucius Hilley, Mar 8, 1998
>
>--Comment by Art Adamson:
>--I adjusted Lucius prime.ex very slightly and added comments, March 9.
>--This prog is now time-wise equivalent to my RDS based primes prog and has
>--reduced memory requirements. They each produce 100000 primes,
>--max prime 1299709 in 1.33 sec for RDS, 1.32 sec for Hilley.
>
>include machine.e
>include get.e
>
>integer temp
>integer n, s -- now using s for indexing and size.
>atom t1, t2
>sequence A, m --Note, Lucius' ingenious use of the A-seq for flags and primes
> --storage. This conserves memory re RDS which uses 2 sequences
> --seq-A for sieve flags and seq-C for primes.
> --On my (Adamson) pentium/120, I can now run a max prime value
> --of 10,000,000. For 15 million, I get a graceful abort, ie
> --program has run out of memory. For my RDS based prog, I get
> --causeway crash occasiomally starting at around 1,000,000.
> --For 10,000,000 input with Lucius prog, I get no crashes,
> --and find the 664579 primes in 10.8 seconds.
>tick_rate(1000) --Seems more accurate and no slower than tick_rate(100)
>puts(1, "\n List All PRIMES, up to that Number ? ... \n")
>m = get(0)
>if m[1] != GET_SUCCESS then
> puts(1, "\n That wasn't a number! ... \n")
> abort(0)
>end if
>t1 = time()
>n = m[2]
>n = floor((n-1) / 2)
>A = repeat(1, n)
>s = 1
>
>for j = 1 to n do --This beautifully compact loop does the business
> if A[j] then
> --temp = 2 * j + 1 11.547 seconds for 10,000,000 max prime
> --temp = j + j + 1 --10.841 " " "
> temp = j temp = temp + j temp = temp + 1 --10.783
> for k = temp + j to n by temp do
> A[k] = 0
> end for
> A[s] = temp
> s = s + 1
> end if
>end for
>
>A = 2 & A[1..s -1]
>t2 = time() - t1
>--? A
>puts(1, "\n\n")
>printf(1, "%7d \t %7d \t %7d \t %7d \n", A[s-3 .. s])
>printf(1, "\n\n There were %d PRIMES ! ... below the number %d \n",
> {s, m[2]})
>printf(1, " \n Total time = %6.3f\n", t2)
>
>Arthur P. Adamson, The Engine Man, euclid at isoc.net
>
Arthur P. Adamson, The Engine Man, euclid at isoc.net
4. Re: Primes
- Posted by MAP <ddhinc at ALA.NET>
Mar 09, 1998
Here's a much better version of the algorithm I posted before.
It takes advantage of a sieve-like process.
------------------------------------------------------------------
-- primes.ex
-- Christopher D. Hickman
-- This works on the premise that all primes after 2 & 3
-- can be located 1 above or below a multiple of 6
-- Is now smarter about what upper and lower limits to
-- run thru... by the time it hits sqrt of max it has
-- eliminated all rejects, and it starts each elimination
-- at p^2, any multiple of p below that would have already
-- been eliminated
-- improves on sieve concept by targeting for elimination
-- only the multiples that fall within (6*n) + or - 1 set.
without type_check
constant max = 1000
sequence all_nums
integer val, is_prime, max_iters, offset, num_primes
max_iters = floor((sqrt(max)+1))
all_nums = repeat(1, max + (max_iters * 4))
for cnt = 5 to max_iters by 6 do
-- lo half... (6 * n) - 1
is_prime = all_nums[cnt]
if is_prime then
offset = cnt + cnt
for cnt2 = cnt * cnt to max by cnt * 6 do
all_nums[cnt2] = 0
all_nums[cnt2 + offset] = 0
end for
end if
-- hi half... (6 * n) + 1
val = cnt + 2
is_prime = all_nums[val]
if is_prime then
offset = val * 4
for cnt2 = val * val to max by val * 6 do
all_nums[cnt2] = 0
all_nums[cnt2 + offset] = 0
end for
end if
end for
puts(1, " 2 3")
num_primes = 2
for cnt = 5 to max by 6 do
-- lo half... (6 * n) - 1
is_prime = all_nums[cnt]
if is_prime then
printf(1, " %d", cnt)
num_primes = num_primes + 1
end if
-- hi half... (6 * n) + 1
val = cnt + 2
is_prime = all_nums[val]
if is_prime then
printf(1, " %d", val)
num_primes = num_primes + 1
end if
end for
printf(1, "\nprimes: %d\n", num_primes)
------------------------------------------------------------------
5. Primes
Here's my primes prog. I'm pretty confident that it is slower than
other algorithms, but I thought it was quite different than all the
others.
constant MAX_PRIME = 10000
integer i, f
sequence primes, sums
i = 2
primes = {i}
sums = primes
while i < MAX_PRIME do
f = find(i, sums)
if f then
sums = sums + primes * (sums <= i)
else
primes = primes & i
sums = sums & i
-- printf(1, "%d, ", {i})
end if
i = i + 1
end while
? primes
--
_____ _____ _____
________ /\ \ /\ \ /\ \
/ \ \ / \____\ / \____\ / \____\
/ _ \____\ / / ___/_ / /____/ / / ___/_
/ / \ |____|/ / /\____\ / \ \ / / /\____\
\ \_/ / / \ \/ / ___/_\ \ \ \ \/ / ___/_
\ /____/ \ / /\ \\/\ \ \ \ / /\ \
\ \ \ \ \/ \____\ \ \ \ \ \/ \____\
\ \ \ \ / / \ \____\ \ / /
\ \____\ \ / / \ / / \ / /
\ / / \ / / \/____/ \ / /
\/____/ \/____/xseal at harborside.com\/____/
6. Re: Primes
- Posted by Arthur Adamson <euclid at ISOC.NET>
Mar 09, 1998
-
Last edited Mar 10, 1998
>From: Arthur Adamson <euclid at isoc.net>
>Subject: Re: Primes
>>> I posted the following PRIME-FINDING times recently. Lucius Hilley
>>>volunteered numerous improvements in the sieve progs and his prog now is
>>>slightly faster than my version of the RDS sieve. Further he has found a way
>>>to use the sieve flags sequence as a place to also store the primes found,
>>>thus easing memory requirements and allowing larger values to be found.
>>> With Lucius' prog, see below, I can run a max prime of 10,000,000 in
>>>10.78 seconds whereas with the RDS version, I an limited to about 1,300,000
>>>before causeway errors take over. Lucius' prog quits gracefully for
>>>15,000,000 input with an out of memory message. I have 32 megs RAM.
>>> Viva La Difference
>>>
>>> I can now take a closer look at some of the other suggestions which
>>>have come in recently and which I have been neglecting while helping iterate
>>>Lucius' prog changes.
>>--------------------------------------------------------------------------
-----
>> Added PM message: I checked Bob Hancocks submission and got 2.50
>seconds. It is added to the timing list. Thanks, Bob. I like the sqrt idea.
>I tried to improve Lucius' prog with id but it didn't work for me. Thanks. Art
>>--------------------------------------------------------------------------
-----
> Further PM Message: I finally tried Chris Hickman's sieve and found
>it is fast, .682 vs Hilley's 1.32. Viva La Chris! Who is next?
> I have replaced Hilley's prog below with Chris's prog (slightly
>modified).
>>>>---------------------------------------
>>>>>>> From: Arthur Adamson <euclid at ISOC.NET>
>>>>>>> Date: Friday, March 06, 1998 10:44 PM
>>>>>> <SNIP>
>>>>>>> > For the first 100000 primes and a Pentium 120, I get times:
>>>>>>> > Seconds
>>>>>>> >Mike Dickey's prime.ex 38.77
>>>>>>> >Carl White's oprime.ex 24.93
>>>>>>> >My mod apaprime.ex 21.83
>>>>>>> >Carl White's sieve 2.73
>>>>>>> >RDSsieve 1.31
>>>>>>> >Chris Hickman's prog 17.08
>>> >Lucius Hilley's sieve 1.31
>>> >Bob Hancock' sieve 2.50
>>> >Pete Eberlein's prog 3.80 for 10000 primes, .008 for Hilley's
>>> >Chris Hickman's sieve .682
>> > William Eiten, was hot on the trail but too busy to follow it.
>>>
>Chris Hickman's Hickman2.ex (slightly modified by using Lucius' idea to save
>on memory...even so, Hilley's still requires less memory).
>Hickman2.ex
>
> Chris says:
>--Here's a much better version of the algorithm I posted before.
>--It takes advantage of a sieve-like process.
>
>------------------------------------------------------------------
>-- primes.ex
>-- Christopher D. Hickman
>
>-- This works on the premise that all primes after 2 & 3
>-- can be located 1 above or below a multiple of 6
>
>-- Is now smarter about what upper and lower limits to
>-- run thru... by the time it hits sqrt of max it has
>-- eliminated all rejects, and it starts each elimination
>-- at p^2, any multiple of p below that would have already
>-- been eliminated
>
>-- improves on sieve concept by targeting for elimination
>-- only the multiples that fall within (6*n) + or - 1 set.
>--Art Adamson, comments, I changed Chris Hickman's prog to have consistent I/O
>--and timing and to save a primes sequence.
>-- I next used Hilley's trick of saving the primes in the front end of the
>--flags sequence. This reduced memory and improved the speed.
>--..and guess what, we have a new winner!!!!
>-- Chris, thanks. I owe you a brass ring. Art Adamson, Mar. 8, 1998
>--Time is .682 vs 1.32 for RDS and Hilley
>
>without type_check
>include get.e
>include machine.e
>--constant max = 7000000 runs out of memory between 7 and 8 million
>--constant max = 1299709
>sequence all_nums, m --input receiver
>integer val, is_prime, max_iters, offset, num_primes, count
>atom t1, t2
>tick_rate(1000)
>puts(1, "\n List All PRIMES, up to what Number ? ... \n")
>m = {}
>m = get(0)
>if m[1] != GET_SUCCESS then
> puts(1, "\n that wasn't a number! ... \n ")
> abort(0)
>end if
>
>t1 = time()
>constant max = m[2]
>
>t1 = time()
>max_iters = floor((sqrt(max)+1))
>all_nums = repeat(1, max + (max_iters * 4))
>
>for cnt = 5 to max_iters by 6 do
> -- lo half... (6 * n) - 1
> is_prime = all_nums[cnt]
> if is_prime then
> offset = cnt + cnt
> for cnt2 = cnt * cnt to max by cnt * 6 do
> all_nums[cnt2] = 0
> all_nums[cnt2 + offset] = 0
> end for
> end if
> -- hi half... (6 * n) + 1
> val = cnt + 2
> is_prime = all_nums[val]
> if is_prime then
> offset = val * 4
> for cnt2 = val * val to max by val * 6 do
> all_nums[cnt2] = 0
> all_nums[cnt2 + offset] = 0
> end for
> end if
>end for
>num_primes = 2
>count = 0
>for cnt = 5 to max by 6 do
>
> -- lo half... (6 * n) - 1
> is_prime = all_nums[cnt]
> if is_prime then
> --printf(1, " %d", cnt) --prints all but 2, 3, and last
> count = count + 1
> num_primes = num_primes + 1
> all_nums[count] = cnt
> end if
> -- hi half... (6 * n) + 1
> val = cnt + 2
> is_prime = all_nums[val]
> if is_prime then
> --printf(1, " %d", val) --prints the last prime
> num_primes = num_primes + 1
> count = count + 1
> all_nums[count] = val
>
> end if
>end for
>t2 = time()
>? (t2 - t1)
>puts(1,"\n")
>printf(1, "\nprimes: %d\n", num_primes)
>------------------------------------------------------------------
>all_nums = {2,3} & all_nums[1..count]
>? all_nums[count-2 .. count+2]
>--? all_nums
>Arthur P. Adamson, The Engine Man, euclid at isoc.net
>
Arthur P. Adamson, The Engine Man, euclid at isoc.net
7. Primes
Irv -
About the proliferation of prime-generating programs:
Sell 'em by the shipload. That's shiPload, please.
More to the point, I don't understand all this excitement about programs
that generate lists of primes. Wouldn't it be more useful to have a program
that determines whether a given number is or is not a prime? You plug in a
number, the program grinds away for a while, and then says, "Yes, it's
prime" or "No, it's composite." In the latter case, if the program would
produce at least one factor, that would be a leg up for determining other
factors; or the program could keep running until it found all the factors.
I have a primitive program that runs on the Hewlett-Packard 32S II pocket
calculator that does the latter. For a large number it takes a long time to
produce the result.
Wally Riley
wryly at mindspring.com
8. Re: Primes
Wallace, you wrote:
>that generate lists of primes. Wouldn't it be more useful to have a program
>that determines whether a given number is or is not a prime? You plug in a
>number, the program grinds away for a while, and then says, "Yes, it's
>prime" or "No, it's composite." In the latter case, if the program would
>produce at least one factor, that would be a leg up for determining other
>factors; or the program could keep running until it found all the factors.
Might be a good subject ofr our next speed contest. But don't
forget, we are interested in beauty as well as usefulness.
Send in your entry to start the ball rolling.
Bye, Art
Arthur P. Adamson, The Engine Man, euclid at isoc.net
9. Re: Primes
>X-Sender: euclid at isoc.net (Unverified)
>To: Arthur Adamson <euclid at isoc.net>
>From: Arthur Adamson <euclid at isoc.net>
>Subject: Re: Primes
>X-Attachments: E:\0NEW\PRIMCMPR\HICKMAN2.EX;
>Date: Tue, 10 Mar 1998 16:39:39 -0500
>
>
>>>From: Arthur Adamson <euclid at isoc.net>
>>>Subject: Re: Primes
I found an error in my timing measure in yesterday's post re
hickman2.ex.
The revised prog below replaces yesterdays prog. The time in the table is
changed from .682 to .714. Sorry for the confusion. Art
>>>> I posted the following PRIME-FINDING times recently. Lucius Hilley
>>>>volunteered numerous improvements in the sieve progs and his prog now is
>>>>slightly faster than my version of the RDS sieve. Further he has found a way
>>>>to use the sieve flags sequence as a place to also store the primes found,
>>>>thus easing memory requirements and allowing larger values to be found.
>>>> With Lucius' prog, see below, I can run a max prime of 10,000,000 in
>>>>10.78 seconds whereas with the RDS version, I an limited to about 1,300,000
>>>>before causeway errors take over. Lucius' prog quits gracefully for
>>>>15,000,000 input with an out of memory message. I have 32 megs RAM.
>>>> Viva La Difference
>>>>
>>>> I can now take a closer look at some of the other suggestions which
>>>>have come in recently and which I have been neglecting while helping iterate
>>>>Lucius' prog changes.
>>>--------------------------------------------------------------------------
>-----
>>> Added PM message: I checked Bob Hancocks submission and got 2.50
>>seconds. It is added to the timing list. Thanks, Bob. I like the sqrt idea.
>>I tried to improve Lucius' prog with id but it didn't work for me. Thanks. Art
>>>--------------------------------------------------------------------------
>-----
>> Further PM Message: I finally tried Chris Hickman's sieve and found
>>it is fast, .682 vs Hilley's 1.32. Viva La Chris! Who is next?
>> I have replaced Hilley's prog below with Chris's prog (slightly
>>modified).
>>>>>---------------------------------------
>>>>>>>> From: Arthur Adamson <euclid at ISOC.NET>
>>>>>>>> Date: Friday, March 06, 1998 10:44 PM
>>>>>>> <SNIP>
>>>>>>>> > For the first 100000 primes and a Pentium 120, I get times:
>>>>>>>> > Seconds
>>>>>>>> >Mike Dickey's prime.ex 38.77
>>>>>>>> >Carl White's oprime.ex 24.93
>>>>>>>> >My mod apaprime.ex 21.83
>>>>>>>> >Carl White's sieve 2.73
>>>>>>>> >RDSsieve 1.31
>>>>>>>> >Chris Hickman's prog 17.08
>>>> >Lucius Hilley's sieve 1.31
>>>> >Bob Hancock' sieve 2.50
>>>> >Pete Eberlein's prog 3.80 for 10000 primes, .008 for Hilley's
>>>> >Chris Hickman's sieve .714
>>>>
>>Chris Hickman's Hickman2.ex (slightly modified by using Lucius' idea to save
>>on memory...even so, Hilley's still requires less memory).
>>Hickman2.ex
>--Here's a much better version of the algorithm I posted before.
>--It takes advantage of a sieve-like process.
>
>------------------------------------------------------------------
>-- primes.ex
>-- Christopher D. Hickman
>
>-- This works on the premise that all primes after 2 & 3
>-- can be located 1 above or below a multiple of 6
>
>-- Is now smarter about what upper and lower limits to
>-- run thru... by the time it hits sqrt of max it has
>-- eliminated all rejects, and it starts each elimination
>-- at p^2, any multiple of p below that would have already
>-- been eliminated
>
>-- improves on sieve concept by targeting for elimination
>-- only the multiples that fall within (6*n) + or - 1 set.
>--Art Adamson, comments, I changed Chris Hickman's prog to have consistent I/O
>--and timing and to save a primes sequence.
>-- I next used Hilley's trick of saving the primes in the front end of the
>--flags sequence. This reduced memory and improved the speed.
>--..and guess what, we have a new winner!!!!
>-- Chris, thanks. I owe you a brass ring. Art Adamson, Mar. 8, 1998
>--Time is .71 vs 1.32 for RDS and Hilley
>
>without type_check
>include get.e
>include machine.e
>--constant max = 7000000 runs out of memory between 7 and 8 million
>--constant max = 1299709
>sequence all_nums, m, primes --input receiver
>integer val, is_prime, max_iters, offset, num_primes, count
>atom t1, t2
>tick_rate(1000)
>puts(1, "\n Save All PRIMES in seq primes, up to what Number ? ... \n")
>m = {}
>m = get(0)
>if m[1] != GET_SUCCESS then
> puts(1, "\n that wasn't a number! ... \n ")
> abort(0)
>end if
>
>t1 = time()
>constant max = m[2]
>
>t1 = time()
>max_iters = floor((sqrt(max)+1))
>all_nums = repeat(1, max + (max_iters * 4))
>
>for cnt = 5 to max_iters by 6 do
> -- lo half... (6 * n) - 1
> is_prime = all_nums[cnt]
> if is_prime then
> offset = cnt + cnt
> for cnt2 = cnt * cnt to max by cnt * 6 do
> all_nums[cnt2] = 0
> all_nums[cnt2 + offset] = 0
> end for
> end if
> -- hi half... (6 * n) + 1
> val = cnt + 2
> is_prime = all_nums[val]
> if is_prime then
> offset = val * 4
> for cnt2 = val * val to max by val * 6 do
> all_nums[cnt2] = 0
> all_nums[cnt2 + offset] = 0
> end for
> end if
>end for
>num_primes = 2
>count = 0
>for cnt = 5 to max by 6 do
>
> -- lo half... (6 * n) - 1
> is_prime = all_nums[cnt]
> if is_prime then
> --printf(1, " %d", cnt) --prints all but 2, 3, and last
> count = count + 1
> num_primes = num_primes + 1
> all_nums[count] = cnt
> end if
> -- hi half... (6 * n) + 1
> val = cnt + 2
> is_prime = all_nums[val]
> if is_prime then
> --printf(1, " %d", val) --prints the last prime
> num_primes = num_primes + 1
> count = count + 1
> all_nums[count] = val
>
> end if
>end for
>primes = {2,3} & all_nums[1..count] --writes primes, truncates,
> --and prepends 2, 3
>t2 = time()
>? (t2 - t1)
>
>puts(1,"\n")
>printf(1, "\nprimes: %d\n", num_primes)
>------------------------------------------------------------------
>
>? primes[count-2 .. count+2]
>--? primes
>--? all_nums
>Arthur P. Adamson, The Engine Man, euclid at isoc.net
>
Arthur P. Adamson, The Engine Man, euclid at isoc.net
10. Re: Primes
- Posted by MAP <ddhinc at ALA.NET>
Mar 10, 1998
-
Last edited Mar 11, 1998
Wallace B. Riley wrote:
<snip>
> More to the point, I don't understand all this excitement about programs
> that generate lists of primes. Wouldn't it be more useful to have a program
> that determines whether a given number is or is not a prime? You plug in a
> number, the program grinds away for a while, and then says, "Yes, it's
> prime" or "No, it's composite." In the latter case, if the program would
> produce at least one factor, that would be a leg up for determining other
> factors; or the program could keep running until it found all the factors.
<snip>
Well, as far as why a generator and not a factorization program,
I thought that would be fairly obvious. The focus here was on the
mathematical principals and program optimization in general rather
than any "usefulness" that prime numbers themselves have. So, why
focus on generation rather than factorization? Surely, with your
programming experience, you know the diffence between processes
that are mostly I/O bound and those that are processor bound. You
"could" process bind a factorization program by throwing randomly
generated large numbers at it, but why would that be any more valid
than the generators?
Here tho (btw, a legitimate variation of "though", it's in
Webster's), is a program that does factorizations if you have such
a need for it. If you type immense numbers into it, you can expect
a couple of seconds before response. Then again, it should beat the
hell out of your calculator.
---------------------------------------------------------------------------
-- Factors.ex
-- Christopher D. Hickman
include get.e
function factors(atom p)
atom r
for cnt = 2 to sqrt(p) do
r = remainder(p, cnt)
if not r then
return sprintf ("%d * %s", {cnt , factors(p/cnt)})
end if
end for
return sprintf("%d", p)
end function
sequence query
atom console
query = {0,0}
while 1 do
console = open("CON", "r") -- allows kb flushing
puts(1, "\nEnter a positive number (0 quits):")
query = get(console)
if query[1] = GET_SUCCESS and
query[2] >= 0 then
if query[2] = 0 then
abort(0)
end if
printf(1, "\nFactors of %d = %s\n",
{query[2], factors(query[2])})
end if
close(console) -- force buffer flush
end while
---------------------------------------------------------------------------
Regards,
Christopher D. Hickman
p.s. I did not go back and check my spelling word for word. So, if I
misspeled anything, I hope it doesn't cause you any great distress!
Surely, Mr. Riley, you could have found a better use for your time.
