Python 3233.py
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
# a number is special if it's the square of a prime
# finding all relevant primes is too slow, use precomputed list instead
primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831,
4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003,
5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279,
5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387,
5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639,
5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693,
5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221,
6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367,
6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761,
6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917,
6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297,
7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411,
7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499,
7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643,
7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723,
7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017,
8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219,
8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387,
8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501,
8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597,
8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741,
8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929,
8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109,
9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199,
9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283,
9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439,
9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533,
9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631,
9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811,
9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887,
9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007,
10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177,
10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271,
10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343,
10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567,
10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657,
10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739,
10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949,
10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059,
11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149,
11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329,
11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443,
11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527,
11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777,
11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833,
11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109,
12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211,
12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289,
12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487,
12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553,
12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641,
12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829,
12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007,
13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187,
13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309,
13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619,
13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697,
13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781,
13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081,
14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197,
14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419,
14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519,
14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593,
14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767,
14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851,
14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947,
14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149,
15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259,
15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319,
15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607,
15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679,
15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881,
15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971,
15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267,
16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381,
16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481,
16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691,
16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811,
16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903,
16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093,
17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317,
17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477,
17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573,
17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669,
17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891,
17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971,
17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059,
18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143,
18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233,
18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313,
18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427,
18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517,
18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637,
18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749,
18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899,
18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009,
19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121,
19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219,
19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319,
19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423,
19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477,
19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571,
19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699,
19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793,
19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891,
19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991,
19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071,
20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149,
20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261,
20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357,
20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443,
20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551,
20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693,
20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771,
20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897,
20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983,
21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067,
21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169,
21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277,
21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383,
21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491,
21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563,
21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647,
21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751,
21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841,
21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943,
21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039,
22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123,
22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229,
22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307,
22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441,
22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543,
22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643,
22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727,
22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817,
22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943,
22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029,
23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099,
23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203,
23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321,
23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447,
23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561,
23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629,
23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743,
23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827,
23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909,
23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007,
24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091,
24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169,
24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281,
24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413,
24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517,
24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659,
24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767,
24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877,
24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977,
24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097,
25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183,
25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303,
25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391,
25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471,
25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603,
25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693,
25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799,
25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913,
25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999,
26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111,
26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203,
26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297,
26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399,
26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497,
26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633,
26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711,
26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801,
26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891,
26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987,
26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077,
27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211,
27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329,
27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449,
27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551,
27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691,
27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767,
27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827,
27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947,
27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051,
28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151,
28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283,
28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403,
28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499,
28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579,
28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649,
28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729,
28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837,
28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933,
28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059,
29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167,
29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251,
29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363,
29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443,
29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573,
29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671,
29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819,
29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921,
29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059,
30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137,
30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241,
30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341,
30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469,
30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559,
30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689,
30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803,
30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871,
30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983,
31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091,
31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183,
31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259,
31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357,
31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511,
31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601,
31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721,
31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817,
31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973,
31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059, 32063,
32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159,
32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257,
32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353,
32359, 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423,
32429, 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531,
32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587, 32603, 32609,
32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717,
32719, 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831,
32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933, 32939,
32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999, 33013, 33023,
33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091, 33107, 33113,
33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203, 33211,
33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331 ]
left = bisect_left (primes, sqrt(l))
right = bisect_right(primes, sqrt(r))
special = right - left
all = r - l + 1
return all - special
369 lines
|
32430 bytes
|
submitted July 28, 2024
|
GitHub
0% comment ratio
|
tab size 4
|
low complexity
Difficulty
This problem is ranked as
and has an acceptance rate of about 28% (100k+ submissions).
Typical patterns to solve this problem:
easy
medium
hard
and has an acceptance rate of about 28% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Math
- Number Theory
I solved 663 easy, 1250 medium and 309 hard problems
AI Disclaimer
Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The Solution class provides a method nonSpecialCount that returns the quantity of integers in the inclusive interval [l, r] which are not the square of a prime number. A “special” number is defined as a perfect square whose square root is a prime. The implementation avoids generating primes on-the-fly and instead relies on a pre-computed list of prime values. By using binary search on this list, the method determines how many prime squares fall inside the requested range and subtracts that count from the total number of integers.
Core Logic
The algorithm follows three essential steps:
- Locate the first prime whose square is at least
l. - Locate the first prime whose square exceeds
r. - Compute the difference between the two positions to obtain the count of special numbers, then subtract from the interval length.
Binary Search for Boundary Indices
left = bisect_left (primes, sqrt(l))
right = bisect_right(primes, sqrt(r))
special = right - leftbisect_left returns the index of the smallest prime p such that p >= sqrt(l).
bisect_right returns the index after the largest prime p satisfying p <= sqrt(r).
The subtraction yields the exact number of primes whose squares lie inside [l, r].
Final Count Computation
all = r - l + 1
return all - specialall represents the total count of integers in the interval. Subtracting special gives the desired count of non-special numbers.
Edge-Case Handling
When l and r are equal, the interval contains a single number. The binary searches correctly identify whether that number is a prime square, resulting in either 0 or 1 being subtracted from all.
If l is larger than the square of the largest prime in the pre-computed list, bisect_left returns an index equal to the length of the list, and bisect_right does the same for r. Consequently, special becomes zero, and the method returns the full interval length, which is correct because no prime squares exist in that range.
When r is smaller than the square of the smallest prime (2^2 = 4), both binary searches yield zero, leading to special = 0. The method therefore counts all numbers in [l, r] as non-special, which matches the definition.
The use of sqrt from the math module ensures that floating-point rounding does not affect the boundary detection because the binary search operates on integer prime values, and the comparison is performed after the square root conversion.
Performance Optimizations
The most significant optimization is the avoidance of on-demand prime generation. Computing all primes up to sqrt(r) for each call would be costly, especially for large r. By embedding a static list of primes that comfortably exceeds the square-root bound for typical problem constraints, the method reduces the prime-related work to a constant-time lookup.
Binary search (bisect_left and bisect_right) runs in logarithmic time relative to the size of the prime list, which is far faster than linear scanning. Because the list is immutable, the search operations benefit from cache locality and minimal overhead.
The arithmetic for the final result (r - l + 1 and subtraction) is performed with simple integer operations, guaranteeing negligible computational cost.
Overall, the combination of a pre-computed prime table and binary search yields a solution that scales efficiently for any interval fitting within the range covered by the stored primes.
written by openai gpt
ELI5 - Simplified Explanation
Imagine you have a big treasure box of numbers. Some of these numbers are what we call special. A number is special if it is made by taking a prime number and multiplying it by itself. Prime numbers are special building blocks like two and three. So the number four is special because it is two times two, and nine is special because it is three times three.
This code looks at a range of numbers stretching from the first number to the last number. It wants to know how many of these numbers are not special. To do this, it first keeps a list of many prime numbers.
The code then looks for the square of those prime numbers that fall inside the range. It uses tools to find where to start and end within that list of primes. By counting how many special numbers live in the range, the code can subtract that count from the total amount of numbers. This leaves behind the count of all the numbers that are not special.
written by google gemini
Code Quality
Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 25
|
median = 4
|
μ = 4.72
|
σ = 2.05
Complexity Analysis
not analyzed yet
Other Solutions
I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||
|---|---|---|---|---|---|---|---|
| author | solutions | ||||||
| www | AlgoMonster | Java | C++ | Python | TS | ||
| WalkCCC | Java | C++ | Python | ||||
| leetcode.ca | Java | C++ | Go | Python | TS | ||
| Progiez | Java | C++ | Python | ||||
| github | charles-wangkai | Java | |||||
| everthis | JS | ||||||
| fsq | C++ | ||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||
| WalkCCC | C++, Python, Java | ||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||
| Progiez | C++, Java, Python | ||||||
| charles-wangkai | Java | ||||||
| everthis | JavaScript | ||||||
| fsq | C++ |
18 links
|
7 authors
|
6 languages
Videos
These are a few popular YouTube videos for this problem:
Developer Coder 9 mins
Find the Count of Numbers Which Are Not Special | Leetcode weekly-contest-408
Programming Live with Larry 13 mins
3233. Find the Count of Numbers Which Are Not Special (Leetcode Medium)
CodeCracker 6 mins
3233 Find the Count of Numbers Which Are Not Special
Road To FAANG 14 mins
Leetcode 3233 | Find the Count of Numbers Which Are Not Special | Weekly Contest 408
Coder on A Farm 7 mins
3233 Find the Count of Numbers Which Are Not Special (leetcode medium)
5 videos
did my crawler come up with invalid videos ? drop me a line.
Similar Problems
- problem 204: Count Primes
1 similar problem
Solved On The Same Day
1 easy
- problem 3194: Minimum Average of Smallest and Largest Elements
2 solutions
July 28, 2024
Fun Facts
This is my longest medium solution with 32430 bytes.
1 fun fact
Extra
There are a few extra pages giving you some insights into my setup:
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality