No... lucky numbers can be composite also ... see this output
35
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25
26 27 28 29 30 31 32 33 34 35
Deleting every number 2 from above.
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35
Deleting every number 3 from above.
1 3 7 9 13 15 19 21 25 27 31 33
Deleting every number 4 from above.
1 3 7 13 15 19 25 27 31
Deleting every number 5 from above.
1 3 7 13 19 25 27 31
Deleting every number 6 from above.
1 3 7 13 19 27 31
Deleting every number 7 from above.
1 3 7 13 19 27
27 is not prime and a lucky number. So the method is fine.
Pratyush Tewari
On Mon, Jan 5, 2009 at 12:30 AM, Vijay Venkat Raghavan N
<mydeares...@gmail.com> wrote:
> Guys this is wrong. Lucky number is basically a prime number if you observe
> the definition carefully, and this approach of determining primality
> obviously won't work.
>
> On Sun, Jan 4, 2009 at 7:12 PM, Channa Bankapur <channabanka...@gmail.com>
> wrote:
>>
>> Here is the C-version of the same. It tells you whether given n is lucky
>> or not.
>> void luckyOrNot(long int n){
>>
>> long int n2 = n;
>> int i= 2;
>> while(n2>=i){
>>
>> if(n2%i == 0){
>>
>> printf("%ld got unlucky when i was %d\n", n, i);
>> break;
>>
>> }
>> n2 = n2 - (n2/i);
>> i++;
>>
>> }
>> if(n2<i){
>> printf("%ld is lucky\n", n);
>> }
>>
>> }
>>
>> Cheers,
>> Channa
>> On Sun, Jan 4, 2009 at 10:34 AM, Sathya Narayanan
>> <sathya.phoe...@gmail.com> wrote:
>> > first n will be the nth number in the sequence.. after each iteration
>> > (intially i=2) the new position of n is calculated as n=n- (n/i) and if
>> > n%i
>> > then u stop.. this goes on until n<i . if n becomes less than i , then
>> > n is
>> > lucky.. this is the approach used in tht perl prog i guess
>> >
>> >
>> > 2009/1/4 daizi sheng <daizish...@gmail.com>
>> >>
>> >> check this perl program, hope it explains the algorithm itself
>> >>
>> >> >>>>>>START OF algo.pl<<<<<<<<<<<<
>> >> use warnings;
>> >> use strict;
>> >>
>> >> sub is_lucky_number
>> >> {
>> >> my ($cur, $n, $last_n, $next_n, $old_n);
>> >>
>> >> $cur = 1; # to remove numbers at $cur, $cur*2, ...
>> >> $n = shift @_; # current index of the input number before removing
>> >> $old_n = $n;
>> >>
>> >> die unless $n > 0;
>> >> $last_n = -1; # index of the input number when after removing
>> >> every $cur-1 number
>> >>
>> >> while($last_n != $n)
>> >> {
>> >> $cur++;
>> >> $next_n = $n - int($n / $cur);
>> >> if($n % $cur == 0)
>> >> {
>> >> #print "$old_n is removed at $cur-th step\n";
>> >> return 0; # input number is not lucky because it will be
>> >> removed at $cur-th step
>> >> }
>> >> $last_n = $n;
>> >> $n = $next_n;
>> >> }
>> >>
>> >> return 1;
>> >> }
>> >>
>> >> foreach my $input (1..100)
>> >> {
>> >> print "$input is lucky\n" if &is_lucky_number($input);
>> >> }
>> >>
>> >> print "Press return to exit\n";
>> >> <>;
>> >>
>> >>
>> >>
>> >> On Sun, Jan 4, 2009 at 2:08 AM, kannan <kven...@gmail.com> wrote:
>> >> >
>> >> > All the numbers from 1 to infinity are written in sequence:
>> >> >
>> >> > 1,2,3,4,5,6,7,8,9,10,11,12,13,14.....
>> >> > in the first iteration, every second number is removed, leaving:
>> >> > 1,3,5,7,9,11,13....
>> >> > in the second iteration, every third number in the above sequence is
>> >> > removed, thus leaving: 1,3,7,9,13....
>> >> > in the third iteration, every fourth number is removed, leaving:
>> >> > 1,3,7,13....
>> >> > like this the process goes on indefinitely.
>> >> > the numbers which are, thus, left are called lucky numbers.
>> >> >
>> >> > Given a number n(can be as big as 18 digits) you must tell if n is a
>> >> > lucky number or not.. how do i proceed?? all that i can think of is a
>> >> > naive implementation which obviously wont work because n can be as
>> >> > big
>> >> > as 18 digits...
>> >> > could you help me or give suggestions on how to proceed....
>> >> > (This question was asked in a practice contest which is over now)
>> >> >
>> >> > >
>> >> >
>> >>
>> >>
>> >
>> >
>> >
>>
>>
>
>
>
> --
> "Success as an entrepreneur is absolute, everything else is relative"
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
