Algorithm
Problem link- https://www.spoj.com/problems/NOSQ/
NOSQ - No Squares Numbers
A square free number is defined as a number which is not divisible by any square number.
For example, 13, 15, 210 are square free numbers, where as 25 (divisible by 5*5), 108 (divisible by 6*6), 18 (divisible by 3*3) are not square free numbers. However number 1 is not considered to be a square and is a squarefree number.
Now you must find how many numbers from number a to b, are square free and also have a digit d inside it.
For example for in the range 10 to 40 te squarefree numbers having digit 3 are 13, 23, 30, 31, 33, 34, 35, 37, 38, 39
Input
The first line contains an integer T, which is the number of test-cases
Then follow T lines, each containing 3 integers a, b and d.
1 <= T <= 20,000
1 <= a <= b <= 100,000
0 <= d <= 9
Output
Print one integer which is the required number as described in the problem statement.
Example
Input: 3 10 40 3 1 100 4 1 100000 7 Output: 10 9 26318
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
MAX = 100005
sq = [0] * MAX
sum = [[0 for i in range(10)] for j in range(MAX)]
for i in range(2, MAX):
for j in range(i * i, MAX, i * i):
sq[j] = 1
for i in range(1, MAX):
for j in range(10):
sum[i][j] = sum[i - 1][j]
if sq[i] == 0:
can = [0] * 10
now = i
while now > 0:
can[now % 10] = 1
now //= 10
for j in range(10):
sum[i][j] += can[j]
T = int(input())
for i in range(T):
a, b, d = map(int, raw_input().split())
print(sum[b][d] - sum[a - 1][d])Input
10 40 3
1 100 4
1 100000 7
Output
9
26318
Demonstration
SPOJ Solution-No Squares Numbers-Solution in C, C++, Java, Python