# C++ sieve instead of brute force

• Instead of doing all that dividing, you can use a sieve instead. Basically, I have an array of bitfields where the bitfield at sieve[i] has bit n set if i is divisible by n.

So the sieve can be set up by iterating over the digits 2 through 9 and then setting the appropriate bits in each of the bitfields. Another trick is that we don't need to keep track of divisibility by 0 or by 1, so there are really only 8 different digits. Conveniently, 8 bits is just the right size to fit into a char instead of having to use a larger integer.

After creating the sieve of lookups, we can go through the desired numbers and test the digits against the sieve value. A further optimization (that I didn't implement) is handling going through the desired numbers to test without having to do the division by 10 either.

``````class Solution {
public:

vector<int> selfDividingNumbers(int left, int right) {
vector<int> result;

unsigned char sieve[right+1];
for (int i=left; i<=right; i++)
sieve[i] = 0;

for (int digit=2; digit<=9; digit++) {
unsigned char mask = (1 << (digit-2));
for (int j=left/digit*digit; j<=right; j+=digit)
sieve[j] |= mask;
}
for (int i=left; i<=right; i++) {
int num = i;
unsigned char sieveBits = sieve[i];
while (num) {
const int newNum = num / 10;
const int digit = num - newNum*10;
num = newNum;
if (digit > 1) {
if (((1<<(digit-2)) & sieveBits) == 0)
goto NextNum;
}
else if (digit == 0) {
goto NextNum;
}
}
result.push_back(i);
NextNum:
;
}

return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.