Sieve of Eratosthenes

News Me wrote:
> I'm wondering, How one goes about determining if a number is a
> multiple of another without dividing?
>

Simple, by using mod (e.g. 6 % 2)


JW

News Me wrote:
> How one goes about determining if a number is a multiple
> of another without dividing?

With subtractions (a *LOT* of subtractions!)
php$ cat mult.php
<?php
function ismultiple($n, $m) {
/* needs validation: $n and $m should be positive integers */
$a = max($n, $m);
$b = min($n, $m);
while ($a > $b) $a -= $b;
if ($a == $b) return true;
return false;
}

$a = $argv[1];
$b = $argv[2];
echo "$a and $b are";
if (!ismultiple($a, $b)) echo ' *NOT*';
echo " multiples\n";
?>

A sample run:
php$ php mult.php 17 1700
17 and 1700 are multiples

And another run, this time with larger values ('time' is the bash
builtin variant)
php$ time php mult.php 17 17000001
17 and 17000001 are *NOT* multiples

real 0m3.453s
user 0m3.430s
sys 0m0.010s


Yes! My computer is a slow 500MHz PC :(

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

"News Me" <newsTWOme@pacifierDOTcom> wrote in message
news:10t6agg3btrfr4d@corp.supernews.com...
> CJ Llewellyn wrote:
> <snip>
> > The sieve of of eratosthenes is a question about multiplication and
> > elimination, not division. If you have to divide something then you're
doing
> > it wrong.
> <snip>
>
> After looking at the explanation of the algorithm here:
>
> http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
>
> I'm wondering, How one goes about determining if a number is a multiple
> of another without dividing?

By finding all the multiples and removing them from your list ;)

2 x 2 = 4

2 x 3 = 6

2 x 4 = 8

2 x 5 = 10

....

3 x 2 = 6

3 x 3 = 9

3 x 4 = 12

3 x 5 = 15

....

Now would you need to do the 4 x ?

You've already calculated that 4 is a product of 2 x 2, the same applies to
6 , 8 , 9 , 12 ..

However 5, 7, 11 haven't shown up on your list, so you need to multiple
those numbers out.

Pedro Graca wrote:
> News Me wrote:
>> How one goes about determining if a number is a multiple
>> of another without dividing?
>
> With subtractions (a *LOT* of subtractions!)

Why not use modulo as I suggested before? Ok, it's still division, but a lot
faster.

Time this function:

function ismultiple($n, $m) {
$a = max($n, $m);
$b = min($n, $m);
return !($a % $b);
}


JW

"Janwillem Borleffs" <jw@jwscripts.com> wrote in message
news:41d3434b$0$33104$abc4f4c3@news.euronet.nl...
> Pedro Graca wrote:
> > News Me wrote:
> >> How one goes about determining if a number is a multiple
> >> of another without dividing?
> >
> > With subtractions (a *LOT* of subtractions!)
>
> Why not use modulo as I suggested before? Ok, it's still division, but a
lot
> faster.

Because the problem is about avoiding division.

Janwillem Borleffs wrote:
> Pedro Graca wrote:
>> News Me wrote:
>>> How one goes about determining if a number is a multiple
>>> of another without dividing?
^^^^^^^^^^^^^^^^

>> With subtractions (a *LOT* of subtractions!)
>
> Why not use modulo as I suggested before?
> Ok, it's still division, but a lot faster.
^^^^^^^^^^^^^^^^^^^

Well ... that's the reason why not use modulo :-)

Had the question been "How to determine if a number is a multiple of
another?", the modulo approach would be the best bet.

> Time this function:
>
> function ismultiple($n, $m) {
> $a = max($n, $m);
> $b = min($n, $m);
> return !($a % $b);
> }

No need to time it. It executes instantaneously.

Maybe the OP is building his own simple processor that cannot do
divisions.
He'll have a very hard time compiling PHP for it though :-)

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com/
== ** ## !! ------------------------------------------------ !! ## ** ==
TEXT-ONLY mail to the whole "Reply-To:" address ("My Name" <my@address>)
may bypass my spam filter. If it does, I may reply from another address!

CJ Llewellyn wrote:
> "News Me" <newsTWOme@pacifierDOTcom> wrote in message
> news:10t6agg3btrfr4d@corp.supernews.com...
>
>>CJ Llewellyn wrote:
>><snip>
>>
>>>The sieve of of eratosthenes is a question about multiplication and
>>>elimination, not division. If you have to divide something then you're
>
> doing
>
>>>it wrong.
>>
>><snip>
>>
>>After looking at the explanation of the algorithm here:
>>
>>http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
>>
>>I'm wondering, How one goes about determining if a number is a multiple
>>of another without dividing?
>
>
> By finding all the multiples and removing them from your list ;)
>
> 2 x 2 = 4
>
> 2 x 3 = 6
>
> 2 x 4 = 8
>
> 2 x 5 = 10
>
> ...
>
> 3 x 2 = 6
>
> 3 x 3 = 9
>
> 3 x 4 = 12
>
> 3 x 5 = 15
>
> ...
>
> Now would you need to do the 4 x ?
>
> You've already calculated that 4 is a product of 2 x 2, the same applies to
> 6 , 8 , 9 , 12 ..
>
> However 5, 7, 11 haven't shown up on your list, so you need to multiple
> those numbers out.
>
>

OK, great! Is 7 a multiple of 62298863484143?

NM

News Me wrote:

> OK, great! Is 7 a multiple of 62298863484143?

No


--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

John Bokma wrote:
> News Me wrote:
>
>
>>OK, great! Is 7 a multiple of 62298863484143?
>
>
> No
>
>

You were supposed to show your math. Without dividing (or modulating).

NM

"News Me" <newsTWOme@pacifierDOTcom> wrote in message
news:10t76p21739dg28@corp.supernews.com...
> John Bokma wrote:
> > News Me wrote:
> >
> >
> >>OK, great! Is 7 a multiple of 62298863484143?
> >
> >
> > No
> >
> >
>
> You were supposed to show your math. Without dividing (or modulating).

if(7 < 62298863484143)
echo "No it's not";