【每日一题20220901】反转后不是本身的素数

兴趣爱好交流 每日一题
1

我们应该选择所有在反转时是不同 素数的素数（因此应该丢弃回文素数）。

例如：13、17 是素数，反过来分别是 31、71，它们也是素数，所以 13 和 17 是“emirps”。但素数 757、787、797 是回文素数，这意味着反转后的数与原来的数相同，因此它们不被视为“emirps”，应该被丢弃。

你的任务

创建一个接收一个参数的函数n ，作为上限，并返回以下数组：

[number_of_emirps_below_n, largest_emirp_below_n, sum_of_emirps_below_n]

例子

find_emirp(10)
[0, 0, 0] ''' no emirps below 10 '''

find_emirp(50)
[4, 37, 98] ''' there are 4 emirps below 50: 13, 17, 31, 37; largest = 37; sum = 98 '''

find_emirp(100)
[8, 97, 418] ''' there are 8 emirps below 100: 13, 17, 31, 37, 71, 73, 79, 97; largest = 97; sum = 418 '''

ps：不要使用素数测试。它会使你的代码非常慢。使用素数生成器或一系列素数生成器创建一组素数。请记住，在集合中搜索比在排序列表或数组中搜索更快

题目难度：一般
题目来源：https://www.codewars.com/kata/55de8eabd9bef5205e0000ba

def find_emirp(n: int) -> list:
    # your code goes here
    return #[amount of emirps in the range(13, n + 1), largest emirp smaller than n, sum of all the emirps of this range.

assert find_emirp(10) == [0, 0, 0]
assert find_emirp(50) == [4, 37, 98]
assert find_emirp(100) == [8, 97, 418]
2 
##简易版
from functools import reduce


def find_emirp(n: int):
	sushu_list=[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]
	new_sushu_list=[sushu_list[i] for i in  range(len(sushu_list)) if sushu_list[i]<=n]##得到传递参数的素数列表
	not_reverse_list=[new_sushu_list[j] for j in range(len(new_sushu_list))
	                  if str(new_sushu_list[j])!=str(new_sushu_list[j])[::-1] and int(str(new_sushu_list[j])[::-1]) in sushu_list]
	sum=0 if len(not_reverse_list)==0 else reduce(lambda x,y:x+y,not_reverse_list)
	max_number=0 if len(not_reverse_list)==0 else reduce(lambda x,y:max(x,y),not_reverse_list)
	result=[len(not_reverse_list),max_number,sum]
	return result
assert find_emirp(10) == [0, 0, 0]
assert find_emirp(50) == [4, 37, 98]
assert find_emirp(100) == [8, 97, 418]
3 
from math import sqrt


def is_prime(num: int) -> bool:
    """
    判断是否为素数（质数）
    质数：大于等于2，不能被它本身和1以外的数整除
    一般，对正整数n，如果用2到n的平方根之间的所有整数去除，均无法整除，则n为质数。
    :param num: 正整数
    :return: True or False
    """
    if num == 1:
        return False
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def find_emirp(n: int) -> list:
    """
    找到反转时是不同素数的素数
    :param n: 正整数
    :return: [number_of_emirps_below_n, largest_emirp_below_n, sum_of_emirps_below_n]
    """
    def gen_emirps(m: int):
        for num in range(m):
            if is_prime(num):
                reverse_num = int(str(num)[::-1])
                if is_prime(reverse_num) and reverse_num != num:
                    yield num

    emirps = set(gen_emirps(n))

    return [len(emirps), max(emirps), sum(emirps)] if emirps else [0, 0, 0]


assert find_emirp(10) == [0, 0, 0]
assert find_emirp(50) == [4, 37, 98]
assert find_emirp(100) == [8, 97, 418]
4 
def find_emirp(n: int) -> list:
    def is_emirps(x:int):
        for i in range(2,x):
            if x%i==0:
                return False
        return True

    res_list=[]
    for i in range(1,n+1):
        if i>9 and str(i)!=str(i)[::-1]:
            if is_emirps(i) and is_emirps(int(str(i)[::-1])):
                res_list.append(i)
    return [len(res_list),max(res_list),sum(res_list)] if res_list!=[] else [0,0,0]

assert find_emirp(10) == [0, 0, 0]
assert find_emirp(50) == [4, 37, 98]
assert find_emirp(100) == [8, 97, 418]
5

方法二：先生成素数表，再从中挑选

    def emirps_list(x:int)->list:
        e_list=[]
        for i in range(2,x+1):
            e=0
            if i==2:
                e_list.append(i)
            for j in range(2,i):
                if i%j==0:
                    break
                else:
                    e += 1
                    if e<i-2:
                        continue
                    else:
                        e_list.append(i)
        return e_list

    res_list=[]
    em_list=emirps_list(int(len(str(n))*'9'))
    n_list=emirps_list(n)
    for i in n_list:
        if i>9 and str(i)!=str(i)[::-1]:
            if int(str(i)[::-1]) in em_list:
                res_list.append(i)
    return [len(res_list),max(res_list),sum(res_list)] if res_list!=[] else [0,0,0]

assert find_emirp(10) == [0, 0, 0]
assert find_emirp(50) == [4, 37, 98]
assert find_emirp(100) == [8, 97, 418]