花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

};

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

By zxi on January 17, 2018

题目大意：求给定范围内，数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10

Output: 4

Explanation:

6 -> 110 (2 set bits, 2 is prime)

7 -> 111 (3 set bits, 3 is prime)

9 -> 1001 (2 set bits , 2 is prime)

10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15

Output: 5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)

11 -> 1011 (3 set bits, 3 is prime)

12 -> 1100 (2 set bits, 2 is prime)

13 -> 1101 (3 set bits, 3 is prime)

14 -> 1110 (3 set bits, 3 is prime)

15 -> 1111 (4 set bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

Solution 1: Brute Force

C++

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private:

bool isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

int bits(int n) {

int s = 0;

while (n) {

s += n & 1;

n >>= 1;

}

return s;

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 30 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

vector<int> p(20, 0);

p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = p[19] = 1;

for (int n = L; n <= R; ++n)

if (p[__builtin_popcountll(n)]) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

constexpr int magic = 665772;

int ans = 0;

for (int n = L; n <= R; ++n)

if (magic & (1 << __builtin_popcountll(n))) ++ans;

return ans;

}

};

Java

// Author: Huahua

// Running time: 39 ms

class Solution {

public int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private boolean isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= (int)Math.sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

private int bits(int n) {

int s = 0;

while (n != 0) {

s += n & 1;

n >>= 1;

}

return s;

}

Python2

"""

Author: Huahua

Running time: 1618 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def isPrime(n):

if n <= 1: return False

if n == 2: return True

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0: return False

return True

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

ans = 0

for n in range(L, R + 1):

if isPrime(bits(n)): ans += 1

return ans

Python2

"""

Author: Huahua

Running time: 1163 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

ans = 0

for n in range(L, R + 1):

if bits(n) in primes: ans += 1

return ans

"""

Author: Huahua

Running time: 667 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

n &= n - 1;

s += 1

return s

ans = 0

while L <= R:

if (665772 >> bits(L)) & 1 > 0: ans += 1

L += 1

return ans

花花酱 LeetCode 204. Count Primes

By zxi on September 9, 2017

Problem:

Count the number of prime numbers less than a non-negative number, n.

Idea:

Sieve of Eratosthenes

Time Complexity:

O(nloglogn)

Space Complexity:

O(n)

Solution:

C++

// Author: Huahua

class Solution {

public:

int countPrimes(int n) {

if (n < 3) return 0;

vector<unsigned char> f(n, 1);

f[0] = f[1] = 0;

for(long i=2;i<=sqrt(n);++i) {

if(!f[i]) continue;

for(long j=i*i;j<n;j+=i)

f[j] = 0;

}

int ans = accumulate(f.begin(), f.end(), 0);

return ans;

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int countPrimes(int n) {

int ans = 0;

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true);

isPrime[0] = false;

if (n > 0) isPrime[1] = false;

for (int i = 2; i < n; ++i) {

if (!isPrime[i]) continue;

++ans;

for (int j = 2 * i; j < n; j += i)

isPrime[j] = false;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 800 ms

"""

class Solution:

def countPrimes(self, n):

if n < 3: return 0

isPrime = [True] * (n + 1)

isPrime[0] = False

isPrime[1] = False

ans = 0

for i in range(2, n):

if not isPrime[i]: continue

ans += 1

for j in range(2 * i, n, i):

isPrime[j] = False

return ans

Posts tagged as “prime”

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

花花酱 LeetCode 204. Count Primes