D57 762. Prime Number of Set Bits in Binary Representation
題目鏈接
762. Prime Number of Set Bits in Binary Representation
題目分析
對給定范圍內(nèi)的每個(gè)整數(shù)，返回其二進(jìn)制形式下，數(shù)字1出現(xiàn)的次數(shù)為質(zhì)數(shù)的次數(shù)港柜。
例如11111篱昔，1出現(xiàn)了5次，5是質(zhì)數(shù)劫灶。
再如10111，1出現(xiàn)了4次，4不是質(zhì)數(shù)和泌。
思路
由于題目固定了范圍為1~106，106次方為1千萬祠肥。小于2^24武氓。即最多只會出現(xiàn)24次1。
由于小于24的質(zhì)數(shù)個(gè)數(shù)有限仇箱，我們直接寫死24以內(nèi)的質(zhì)數(shù)县恕。
對每一個(gè)數(shù)字，計(jì)算1出現(xiàn)的次數(shù)剂桥。再判斷出現(xiàn)次數(shù)是否在這個(gè)質(zhì)數(shù)數(shù)組內(nèi)忠烛。
存在則符合題目要求的數(shù)字，否則不計(jì)入該數(shù)字权逗。
最終代碼
<?php
class Solution {
/**
* @param Integer $L
* @param Integer $R
* @return Integer
*/
function countPrimeSetBits($L, $R) {
$primes = [2,3,5,7,11,13,17,19,23];
$nums = range($L,$R);
$primeOnes = 0;
foreach($nums as $num){
$ones = array_filter(str_split(decbin($num)), function($val){
return $val == '1';
});
if(in_array(count($ones),$primes)){
$primeOnes++;
}
}
return $primeOnes;
}
}
若覺得本文章對你有用况木，歡迎用愛發(fā)電資助垒拢。
