Numbers in range [ L , R ] such that the count of their divisors is both even and prime | Javascript implementation of the approach ; stores whether the number is prime or not ; stores the count of prime numbers less than or equal to the index ; create the sieve ; Create a boolean array " prime [ 0 . . n ] " and initialize all the entries as true . A value in prime [ i ] will finally be false if ' i ' is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; stores the prefix sum of number of primes less than or equal to ' i ' ; create the sieve ; ' l ' and ' r ' are the lower and upper bounds of the range ; get the value of count ; display the count
var MAX = 1000000 ; var prime = Array ( MAX + 1 ) . fill ( true ) ; var sum = Array ( MAX + 1 ) . fill ( 0 ) ; function SieveOfEratosthenes ( ) { prime [ 1 ] = false ; for ( var p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] ) { for ( var i = p * 2 ; i <= MAX ; i += p ) prime [ i ] = false ; } } for ( var i = 1 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) sum [ i ] = 1 ; sum [ i ] += sum [ i - 1 ] ; } } SieveOfEratosthenes ( ) ; var l = 3 , r = 9 ; var c = ( sum [ r ] - sum [ l - 1 ] ) ; document . write ( " " + c ) ;