Help with rational numbers?

Question 1:
How many distinct rational numbers p/q exist, when p and q are positive integers, p <= q, and q <= N, where N is a given natural number?

Question 2:
What is the next greater such number from a given rational number r/s with the same properties?

For Q1 I can only think of a naive algorithm that iterates over every denominator and adds newly encountered rationals to a list, if it's not equal to any already in the list, an finally outputs the size of that list. This would run in horrible O(N^2). Yet there's certain sense of familiarity in the first few values of this counting function:
1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43 ...

q          p/q such that p <= q
1          1/1
2          1/1 1/2 2/2
3          1/1 1/2 2/2 1/3 2/3 3/3
4          1/1 1/2 2/2 1/3 2/3 3/3 1/4 2/4 3/4 4/4
.
.
.

>>3
except that
1/1 = 2/2 = 3/3 = 4/4
1/2 = 2/4
You're counting the same numbers multiple times.

Another related question:
Is there a way to get the ordered sequence of rational numbers with a maximum limit N on the denominator, without using explicit sorting.
E.g. for N=5, the sequence would be
0  1/5  1/4  1/3  2/5  1/2  3/5  2/3  3/4  4/5  1 ...

I believe that question 1 is related to  http://www.research.att.com/~njas/sequences/A018804
as long as you distinguish between equivalent forms such as 3/3 and 4/4.  You can make your own list of counts for the case of not counting previous equivalent forms and see if the sequence is known by doing a search at that site.