How many integers from 1 to 2003 inclusive have an odd number of disti

Question

How many integers from 1 to 2003 inclusive have an odd number of distinct positive divisors?

(A) 100 
(B) 75 
(C) 50 
(D) 46 
(E) 44

broall · Answer

If  N=p_1^{q_1} 	imes p_2^{q_2} 	imes ... 	imes p_n^{q_n} , where  p_1, p_2, ..., p_n  are distinct prime divisors, then the number of factors of  N  is  (1+q_1)(1+q_2)...(1+q_n)

If  N  has an odd number of distinct divisors, then  (1+q_1)(1+q_2)...(1+q_n)  is odd, so  q_1, q_2, ..., q_n  are all even.

So, we simply count the number of integers from 1 to 2003 that these numbers are squared.
For example,  1^2  has only 1 positive divisors.
 2^2  has 3 positive divisors 1, 2, and 4.
 3^2  has 3 positive divisors 1, 3, and 9.
 4^2=2^4=16  has 5 positive divisors 1, 2, 4, 8, 16.
 6^2 =2^2 	imes 3^2=36  has 9 positive divisors 1, 2, 3, 4, 6, 9, 12, 18, 36.

Note that  44^2=1936  and  45^2=2025 , so these numbers are  1^2, 2^2,..., 44^2 . There are 44 numbers like them.

The answer is E

In this solution, we count only squared number. What about other number is formed by even exponent like  k^4, k^6, k^8,... ?
Note that  k^4=(k^2)^2 , and we've already counted  k^2 . For example, counting  2^4  means counting  (2^2)^2=4^2 .
Also,  k^6=(k^3)^2 . For example, counting  3^6  means counting  (3^3)^2=27^2 .

SI777 · Answer

a perfect square always have odd number of distinct factors.

So the question is basically asking us to find how many numbers have got squares less than 2003.

Answer E. back-solving

Rest of the numbers exceed 2003.

gillyelephant · Answer

This seems like a level 700 question

Posted from my mobile device

auradediligodo · Answer

Hi everyone,

How many integers from 1 to 2003 inclusive have an odd number of distinct positive divisors?

(A) 100 
(B) 75 
(C) 50 
(D) 46 
(E) 44

Perfect squares are number with odd number of factors.
A perfect square is a number with even powers among its prime factors.
So we can just list all the perfect squares until we overpass 2003

1^2=1
2^2=4
3^2=9
44^2=1936

You can stop here because 45^2 is way beyond 2003. 
 Hence option E is the correct option.

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

How many integers from 1 to 2003 inclusive have an odd number of disti

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

How many integers from 1 to 2003 inclusive have an odd number of disti

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards