RE: prime numbers question
- From: "Sina Bahram" <sbahram@xxxxxxxxx>
- To: <programmingblind@xxxxxxxxxxxxx>
- Date: Sun, 16 Aug 2009 13:28:12 -0400
Well, sense other members pretty much just gave away the answer, I'll go
ahead with my suggestion.
There is a quadratic speedup of this problem in it's naïve implementation.
That is, you simply iterate until the square root when determining potential
divisors. The reason for this is pretty obvious, but in way of example,
examine the following.
Is 25 prime?
Let's test 2, nope
Let's test 3, nope
Let's test 4, nope
Let's test 5, oops, we got one, it's not prime
Let's do another example, like 31:
Let's test 2, nope
Let's test 3, nope
Let's test 4, nope
Let's test 5, nope
The reason for this is quite easy to understand,.
If we have a number, and we posit it can be divided by another number, then
there are several possibilities.
Either it is comprised of a number times itself.
Or it is comprised of a number times another number.
Since the largest a single multiple of a number can be is the square root of
that number, the other number must either be the same number, E.G. the
square root, or a smaller number.
Also, the most efficient way of doing this problem simply is the Sieve of
Eratosthenes.
Have fun.
Take care,
Sina
-----Original Message-----
From: programmingblind-bounce@xxxxxxxxxxxxx
[mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Chris Hofstader
Sent: Sunday, August 16, 2009 1:21 PM
To: programmingblind@xxxxxxxxxxxxx
Subject: Re: prime numbers question
I'm aware of better optimizations but figured I'd toss out the most
obvious so as to possibly tease the better solutions out of the group...
this is one of those problems that even we old buggers who went to
college in the seventies would try to optimize.
cdh
On Aug 16, 2009, at 9:07 AM, Sina Bahram wrote:
> *smile*, this is actually a very minimal optimization ... There is a
> far
> better, and just as easy, optimization, but I was trying to
> specifically not
> say it until we receive some responses, per hapse some attempts at
> code, and
> so on.
>
> *smile*
>
> Take care,
> Sina
>
> -----Original Message-----
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Chris
> Hofstader
> Sent: Sunday, August 16, 2009 8:55 AM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: Re: prime numbers question
>
> One optimization to Sina's description is that you can automatically
> eliminate all even numbers as all are divisible by 2.
> On Aug 16, 2009, at 8:46 AM, Sina Bahram wrote:
>
>> Start by defining what a prime number is ... I'm going to assume you
>> know
>> some of this, but I won't give the full answer here.
>>
>> Very rough, non-mathematical definition:
>>
>> A prime number is any number greater than 1, which is evenly
>> divisible by
>> only itself and 1.
>>
>> The first few are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on.
>>
>> So if I was a computer, and I'm given a number, I have to figure out
>> if it
>> is evenly divisible by only itself and one. How would I go about
>> finding
>> out what a number is evenly divisible by?
>>
>> Hint:
>>
>> Evenly divisible is another way of saying that when you divide a
>> number by a
>> divisor, the remainder is 0. If this was in print, I would have
>> underlined
>> the word remainder.
>>
>> Hope this puts you on the right track?
>>
>> Take care,
>> Sina
>>
>> -----Original Message-----
>> From: programmingblind-bounce@xxxxxxxxxxxxx
>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Marvin
>> Hunkin
>> Sent: Sunday, August 16, 2009 8:14 AM
>> To: programmingblind@xxxxxxxxxxxxx
>> Subject: prime numbers question
>>
>> hi.
>> have to do a assignment in cz++.
>> where you enter a number.
>> then it will spit out if it is a prime number or a composite number.
>> any ideas how i code this.
>> cheers Marvin.
>> E-Mail: startrekcafe@xxxxxxxxx
>> Msn: startrekcafe@xxxxxxx
>> Skype: startrekcafe
>> to subscribe to the Jaws Australia group send a blank message to
>> JawsOz-subscribe@xxxxxxxxxxxxxxx
>> Visit my Jaws Australia Group at http://groups.yahoo.com/groups/
>> JawsOz/
>>
>>
>> __________
>> View the list's information and change your settings at
>> //www.freelists.org/list/programmingblind
>>
>> __________
>> View the list's information and change your settings at
>> //www.freelists.org/list/programmingblind
>>
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
Other related posts:
