28

I am a beginner and I've been trying to run a program that prints all the numbers from 1 to N (user input) except for those that are divisible by 3 and 7 at the same time. What my code does instead, however, is that it prints the numbers from 1 to N except for those that are divisible by 3 or 7. I examined it for a while and I have no idea why it does that. Please explain to me where I'm going wrong.

static void Main(string[] args)
{
    int n = 0;
    int a = 0;
    n = Convert.ToInt32(Console.ReadLine());
    while (a <= n)
    {
        a++;
        if (a % 3 != 0 && a % 7 != 0)
        {
            Console.WriteLine(a);
        }
    }
    Console.ReadKey();
}

When I reverse the signs of the if statement to == the && operator works properly, but if the sign is != it simply acts like an || operator, so that confuses me even more. The issue is most likely in the condition, but I can't see what is wrong with it.

5
  • 32
    As a side note, a number is divisible by both 3 and 7 if, and only if, it is divisible by 21.
    – ach
    Sep 10, 2015 at 10:51
  • 2
    !(a%3==0 && a%7==0)
    – geometrian
    Sep 10, 2015 at 18:43
  • 1
    @AndreyChernyakhovskiy: Better generalization is - a number is divisible by both a and b, if it is divisible by LCM of a and b. Sep 10, 2015 at 20:21
  • @displayName: meta.stackexchange.com/a/19479/135695 Also, freehand drawn Venn diagrams are preferred: meta.stackexchange.com/a/19775/135695
    – Ben Voigt
    Sep 10, 2015 at 21:11
  • x = a%3 == 0 (divisible by three), y = a%7 == 0 (divisible by 7). You want !(x&&y) = !x || !y, instead of !x && !y which you have in code. You just need to study some mathematical logic.
    – Cthulhu
    Sep 11, 2015 at 8:39

10 Answers 10

95

"Except numbers that are divisible by 3 and 7 at the same time" can be broken down as follows:

"divisible by 3 and 7 at the same time" can be expressed as:

"(divisible by 3 and divisible by 7)"

"Except" can be expressed as "Not".

So you get:

Not (divisible by 3 and divisible by 7)

"divisible by 3" is (a % 3) == 0

"divisible by 7" is (a % 7) == 0

Giving:

Not ( (a % 3) == 0 and (a % 7) == 0)

In C# Not becomes ! and and becomes &&, so you can write the whole thing in C# as:

if (!((a % 3) == 0 && (a % 7) == 0))


Compare with your incorrect:

if (a % 3 != 0 && a % 7 != 0)

This latter is incorrect because it means:

if (the number is not divisible by 3) and (the number is not divisible by 7).

i.e. it means "Print the number if it is neither divisible by 3 nor divisible by 7", which means "don't print the number if it's divisible by 3 or 7".

To see why, first consider the number 6:

6 is not divisible by 3? = false (because 6 *is* divisible by 3)
6 is not divisible by 7? = true (because 6 is *not* divisible by 7)

So this resolves to if false and true which is, of course, false.

This result also applies to any other number divisible by 3, so no numbers divisible by 3 will be printed.

Now consider the number 14:

14 is not divisible by 3? = true (because 14 is *not* divisible by 3)
14 is not divisible by 7? = false (because 14 *is* divisible by 7)

So this resolves to if true and false which is, of course, false.

This result also applies to any other number divisible by 7, so no numbers divisible by 7 will be printed.

Hopefully you can see why it's wrong now. If not, consider this equivalent example:


Suppose we have four people, Tom the Carpenter, Dick the Carpenter, Harry the Butcher and Tom the Butcher.

This question is equivalent to the one you're asking:

 Name every person who is (not called Tom and is not a Butcher)

And you should be able to see that this the same as asking:

Name every person except (anyone called Tom or anyone who is a Butcher)

In both cases, the answer is Dick the Carpenter.

The question you should have asked is:

Name every person except (anyone called Tom who is also a butcher)

To which the answer is Tom the Carpenter, Dick the Carpenter and Harry the Butcher.


Footnote: De Morgan's laws

The second law states that:

"not (A or B)" is the same as "(not A) and (not B)"

This is the equivalent of my example above where:

Name every person except (anyone called Tom or anyone who is a Butcher)

is the equivalent to:

Name every person who is (not called Tom and is not a Butcher)

where A is anyone called Tom and B is anyone who is a butcher and not is written as except.

9
  • An excellent response. However, in theory, shouldn't " if (a % 3 != 0 && a % 7 != 0) " also be correct? My logical not is just 2 "!=" signs instead of a single "!" sign so I find this to be pretty confusing.
    – Ornstein
    Sep 10, 2015 at 12:31
  • @Ornstein I have added more information to explain why that's wrong. Sep 10, 2015 at 12:43
  • 13
    Though the thorough explanation is appreciated, I believe the answer would benefit from explaining the theory that's going on under the hood with the logical statements i.e. De Morgan's Law.
    – Leon7C
    Sep 10, 2015 at 18:35
  • 2
    @Leon7C I think such an explanation would be beyond the scope of an answer here. Someone already linked the Wiki article on De Morgan's laws (although I fear it would possibly be too complicated for the OP, at least at this stage). My example with Tom, Dick and Harry was intended to provide a basic introduction to the logic for the OP's specific issue. However, I will add a footnote. Sep 10, 2015 at 21:08
  • 1
    Almost thought you wouldn't mention De Morgan in this long answer at all. :) Sep 11, 2015 at 7:26
73

You should read De Morgan's laws

"not (A and B)" is the same as "(not A) or (not B)"

also,

"not (A or B)" is the same as "(not A) and (not B)".

a % 3 != 0 && a % 7 != 0 is true when a is not divisible by 3 (a % 3 != 0) and not divisible by 7 (a % 7 != 0). So all as which are divisible by 3 or 7 (3,6,7,9,12,14,...) makes the whole expression false. You can rephrase it like !(a % 3 == 0 || a % 7 == 0)

11
  • What I want is for the condition to be true when a is not divisible by 3 and 7, but it still behaves as if it's either 3 or 7. I replaced the condition with "if (!(a % 3 == 0 && a % 7 == 0))" and it worked, but I am still not quite sure why my initial condition didn't do the same.
    – Ornstein
    Sep 10, 2015 at 10:57
  • @Ornstein Try reading your initial condition out loud; you should end up with something like : Print a as long as a does not divide 3 and also a does not divides 7. For a to be printed both parts of the conjunction has to be true, so the cases where a is not printed are the cases where at least one of the parts are false. That is a divides 3 or a divides 7. This is what De Morgan's laws tells you.
    – Taemyr
    Sep 10, 2015 at 11:54
  • 1
    There is a simple fix to avoid such awkward situations, use more parenthesis than strictly necessary.
    – Caridorc
    Sep 10, 2015 at 12:00
  • @Dukeling ( (a % 3 != 0) && (a % 7 != 0) )
    – Caridorc
    Sep 10, 2015 at 12:10
  • 2
    this should be the accepted answer - it's really not about the operator, it's the concept of boolean logic in general that OP wasn't getting. Sep 10, 2015 at 20:03
9

All you really need is:

if ((a%21) != 0) Console.WriteLine(a);

Explanation: The numbers that are divisible by both a and b are essentially the numbers divisible by the LCM of a and b. Since, 3 and 7 are prime number, you are basically looking for numbers that are not divisible by 3*7.

7
  • 1
    It took a second to realize that you had a point that no one else had made.
    – kleineg
    Sep 10, 2015 at 20:32
  • 1
    @kleineg it was made in a comment. But yes, this is by far the best way to solve this problem. All those posts that clearly and extensively explain how to make the badly designed program work... sad. Sep 11, 2015 at 18:00
  • @Yakk I agree. It does makes sense that people answered the question at face value (although a lot of the answers are redundant) because it promotes an understanding of De Morgan's laws, which would be helpful when negating a conditional statement. But it is also true that in this case there does exist a... more elegant solution. Thumbs and votes up for that.
    – kleineg
    Sep 11, 2015 at 18:08
  • @Yakk: I posted the answer before reading the comment, then I read the comment and then posted my comment there too. The highest upvoted comment on the question is actually misleading. It's working because 3 and 7 are prime. Won't work for, let's say 4 and 6. For non coprime numbers, it's not the multiplication but, as I said, the LCM that is to be used. Sep 11, 2015 at 18:08
  • 4 * 6 is 24. But the first number filtered by 24 would be 24 itself while 12 is a multiple of both 4 and 6 and should be filtered as well. And that's because 4 and 6 aren't coprimes. Sep 11, 2015 at 18:12
9

Should be:

if ( !(a % 3 == 0 && a % 7 == 0) )
{
    Console.WriteLine(a);
}

It means exactly: all the numbers except for those that are divisible by 3 and 7 at the same time.

You could also rephrase it as:

if ( a % 3 != 0 || a % 7 != 0 )
{
    Console.WriteLine(a);
}
2
  • Thank you, your solution worked. The second piece of code seems a bit weird to me but it makes sense. Can you explain to me in a little more detail why your first statement works but mine doesn't, if possible?
    – Ornstein
    Sep 10, 2015 at 11:04
  • @Ornstein Using words as @MatthewWatson did, your statement said if a is not divisible by 3 AND a is not divisible by 7, but @user2622016's answer says if it's not true that a is divisible by BOTH 3 and 7. A number like 6 would not pass your check, but it would pass @user2622016's check. If you distribute the not at the beginning of the @user2622016's code, you get the second piece of code. It's almost identical to the code that you originally posted, but, when distributing nots, we need to change && to || and change || to &&.
    – A N
    Sep 10, 2015 at 15:36
9

What you said:

   if not (divisible by 3 and divisible by 7) then print

What you wrote:

   if not divisible by 3 and not divisible by 7 then print

Not the same thing. Aristotle thought of it first, Augustus De Morgan wrote the laws 158 years ago, apply the not operator to the operands and invert the logical operation:

   if not divisible by 3 or not divisible by 7 then print

Which produces:

   if (a % 3 != 0 || a % 7 != 0)

Or just write it the way you said it:

   if (!(a % 3 == 0 && a % 7 == 0))
3
  • The first part makes a lot of sense. After you mention the logical OR operator I just get lost. How could an OR operator possibly encompass a situation where two values need to answer a condition in the same time? I understand that what you're saying is correct, but I don't see why. I know that De Morgan's laws state lots about inverting operators, but an OR operator satisfying a simultaneous condition sounds absolutely confusing and impossible to me. Could you give me a simple explanation on that if you wouldn't mind?
    – Ornstein
    Sep 10, 2015 at 12:42
  • Not sure I can understand your hangup, I've been doing this for too long. I'm guessing you got confused by the replacement of == by !=. Maybe it is easier to get when you work this out with variables of type bool instead. Like bool divisiblyBy3 = a % 3 == 0; same for divisiblyBy7 and then write the if() statement. Other than that, Mister DeMorgan is your friend, always keep him handy. Sep 10, 2015 at 13:11
  • Some other answers managed to fill in the gaps and I understand it now. It's just that using the OR operator makes the way of deciding whether a is divisible by 3 and 7 radically different than when using the AND operator. Also, perhaps I should've re-read the task itself a couple more times because now that I did it I managed to grasp the concept more easily. Either way, your answer in combination with 2 others managed to help me understand the issue. Thank you very much for your help and your time!
    – Ornstein
    Sep 10, 2015 at 13:16
5

Looking at your conditional statement's Truth Table you can see that if

 X(NOT multiple of 3) Y(NOT multiple of 7)   X && Y
      true                   true            'a' printed as it is not a multiple of either
      true                   false           'a' not printed, it is multiple of 7
      false                  true            'a' not printed, it is multiple of 3
      false                  false           'a' not printed, it is multiple of both 

That is why all the multiples of 3 or 7 or 21 are not printed.


What you want: Numbers, that are

  • not a (multiple of 3 AND 7). And that is
  • !(a%3==0 && a%7==0) or even further simplified to
  • !(a%21 == 0) or even
  • (a%21 != 0)
1
  • 1
    I think this is really the primary answer to the question. The && operator is doing exactly what it says it will do; just follow the evaluation of the expression step by step.
    – David K
    Sep 12, 2015 at 14:06
4

a % b != 0 means "a is not divisible by b".

If something is not divisible by 3 and not divisible by 7, it's divisible by neither. Thus if it's a multiple of 3 or a multiple of 7, your statement will be false.

It often helps to think of logic in terms of real-world things:
(keep in mind that true and false == false and true or false == true)

The ocean is blue (a is divisible by 3).
The ocean is not yellow (a is not divisible by 7).

What you have:
The ocean is not blue and the ocean is not yellow - this is false (you want this to be true).

What you want:
The ocean is not (blue and yellow) - this is true (the ocean is only blue, not both blue and yellow).
The ocean is not blue or the ocean is not yellow - this is true (the ocean is not yellow).

The equivalent of the last 2 statements would be:

!(a % 3 == 0 && a % 7 == 0)
(a % 3 != 0 || a % 7 != 0)

And you can convert one to the other using De Morgan's laws.

1

If you don't know how to implement an algorithm, try breaking it down into obviously correct functions that each implement part of the algorithm.

You want to "print all the numbers from 1 to N (user input) except for those that are divisible by 3 and 7 at the same time." Old timers can quickly spit out a correct and efficient implementation using logical operators. As a beginner, you may find it helps to break it down into pieces.

// write out the highest level problem to solve, using functions as
// placeholders for part of the algorithm you don't immediately know
// how to solve
for ($x = 1; $x <= $N; $x++) {
    if (is_not_divisible_by_3_and_7($x)) {
        print "$x\n";
    }
}

// then think about the function placeholders, writing them out using
// (again) function placeholders for things you don't immediately know
// how to do
function is_not_divisible_by_3_and_7($number) {
    if (is_divisible_by_3_and_7($number)) {
        return false;
    } else {
        return true;
    }
}

// keep repeating this...
function is_divisible_by_3_and_7($number) {
    if (is_divisible_by_3($number) && is_divisible_by_7($number)) {
        return true;
    } else {
        return false;
    }
}

// until you have the simplest possible functions
function is_divisible_by_3($number) {
    if ($number % 3 === 0) {
        return true;
    } else {
        return false;
    }
}

function is_divisible_by_7($number) {
    if ($number % 7 === 0) {
        return true;
    } else {
        return false;
    }
}

This is easier to follow, because each function does one thing and the function name describes exactly that one thing. This also satisfies the first rule of programming: correct code comes first.

You can then start to think of making the code better, where better can mean:

  • fewer lines of code
  • less calculations
  • more comments

Taking this approach with the code above, an obvious improvement is to replace is_divisible_by_3 and is_divisible_by_7 with a generic function:

function is_divisible_by_n($number, $divisor) {
    if ($number % $divisor === 0) {
        return true;
    } else {
        return false;
    }
}

You can then replace all the big, bulky if x return true else return false with the ternary operator, which gets you to:

function is_divisible_by_n($number, $divisor) {
    return ($number % $divisor === 0) ? true : false;
}

function is_divisible_by_3_and_7($number) {
    return (is_divisible_by_n($number, 3) && is_divisible_by_n($number, 7)) ? true : false;
}

function is_not_divisible_by_3_and_7($number) {
    return (is_divisible_by_3_and_7($number)) ? false : true;
}

Now, notice that is_not_divisible_by_3_and_7 looks exactly like is_divisible_by_3_and_7, except the returns are switched, so you can collapse those into one method:

function is_not_divisible_by_3_and_7($number) {
    // look how it changed here ----------------------------------------------VVVVV - VVVV
    return (is_divisible_by_n($number, 3) && is_divisible_by_n($number, 7)) ? false : true;
}

Now, rather than using ternary operators you can leverage the fact that comparisons themselves return a value:

function is_divisible_by_n($number, $divisor) {
    // this expression returns a "truthy" value: true or false
    //     vvvvvvvvvvvvvvvvvvvvvvvvvv
    return ($number % $divisor === 0);
}

function is_not_divisible_by_3_and_7($number) {
    // also returns a truthy value, but inverted because of the !
    //    vvv
    return ! (is_divisible_by_n($number, 3) && is_divisible_by_n($number, 7));
}

Finally, you can just mechanically replace the function calls with their equivalent logical operations:

for ($x = 1; $x <= $N; $x++) {
    // all I did below was copy from the function, replace variable names
    //  v  vvvvvvvvvvvvvv    vvvvvvvvvvvvvv
    if (! (($x % 3 === 0) && ($x % 7 === 0))) {
        print "$x\n";
    }
}

As bonus points, you can then apply DeMorgan's rule, to distribute the not through the expression:

for ($x = 1; $x <= $N; $x++) {
    if ($x % 3 !== 0 || $x % 7 !== 0) {
        print "$x\n";
    }
}

Additionally, you might observe that two co-prime numbers have common factors if and only if they have common factor N times M, so:

for ($x = 1; $x <= $N; $x++) {
    if ($x % (3*7) !== 0) {
        print "$x\n";
    }
}

You can take this further by using your language's features to compact the expression more:

array_walk(
    range(1, $N),
    function ($x) {
        if ($x % 21 !== 0) print "$x\n";
    }
);

And so on. The point is that you start by making your code correct, then you make it better. Sometimes making code correct means thinking long and hard. Sometimes it just means writing it out in very small, very explicit steps.

0

&& behaves differently to ||

To understand the difference, it may help to do some tests with simpler expressions:

if (true && false)
if (true || false)

So, your problem is with understanding the other operators in your code (!= and %).

It often helps to split conditions into smaller expressions, with explanations:

bool divisbleBy3 = (a % 3 == 0);
bool divisbleBy7 = (a % 7 == 0);

if (divisbleBy3 && divisibleBy7)
{
    // do not print
}
else
{
    // print
}
5
  • 1
    Yes, the result is different. That's the whole point of having two different operators, if the result was the same one of the operators would be redundant. What is your point?
    – SJuan76
    Sep 10, 2015 at 10:54
  • Well, the point is to answer the question. Look at the title... :-)
    – user1023602
    Sep 10, 2015 at 11:40
  • You've answered the title then, but not the question
    – Liam
    Sep 10, 2015 at 12:31
  • Actually this doesn't even answer the title?!
    – Liam
    Sep 10, 2015 at 12:32
  • @buffjape I know the difference between logical AND and logical OR. The issue is that in my program, the logical AND behaves like a logical OR, at least as far as my understanding goes.
    – Ornstein
    Sep 10, 2015 at 12:32
-1

Obviously && and || are different.

It states: if (true && false) = false if (true || false) = true

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.