あるNに対してa^b(a,b≧2)と表せないようなN以下の数 / sympy.factorint()を用いた場合

#問題

AtCoder Beginner Contest 193 / C問題より

#試した手法
AtCoderでは、どうやらsympyライブラリは使えないようですが、パッと思いついたのでこれを用いて問題解決を図ります。
1~Nの数iに対し、それぞれをsympy.factorint(i).keys()及び.values()を行うことでaとbのリストをそれぞれ生成します。また、辞書の長さlに対し、lが2以上の場合は、bの要素が全て一致し、かつそれらが全て2以上であった場合、そのような数はa^bの形で表せると考えました。またlが1の時は、bがシンプルに2以上であればそのような数はa^bの形で表せると考えました。そしてこれらを逐一カウントし、最後にNから引いた数が問題の答えだという要領です。

以上の考察に従って書いたのが下のコードです：

Python
1from sympy import factorint
2
3N = int(input())
4
5cnt = 0
6
7for i in range(0, N + 1):
8	
9	a = list(factorint(i).keys())
10	b = list(factorint(i).values())
11	l = len(factorint(i))
12
13	if l > 1:
14	    if all(el >= 2 for el in b) == True and len(list(set(b))) == 1:
15	    	cnt += 1
16
17	elif l == 1:
18		if all(el >=2 for el in b) == True:
19			cnt += 1
20
21print(N - cnt)

#質問
sympyがAtCoderの指定ライブラリでない以上、採点の手段がないのですが、例として数例の問いと答えが上がっていたのでそれらを試したところ、例えばN=8では6が正しく出力されたのですが、N=100000では本来99634が出力されるはずだったのですが、何故か出力されたのは99743とだいぶずれた数値でした。見落としの可能な限りないように細心の注意を払って構築したのですが、どのような箇所に誤りがあると考えられますでしょうか。幾分雑な形の質問とはなってしまいましたが、お力添え頂ける箇所がございましたら、何卒ご教授のほどよろしくお願い申し上げます。