[WeChall] Prime Factory (Training, Math) 的解决方法

题目

Your task is simple:
Find the first two primes above 1 million, whose separate digit sums are also prime.
As example take 23, which is a prime whose digit sum, 5, is also prime.
The solution is the concatination of the two numbers,
Example: If the first number is 1,234,567
and the second is 8,765,432,
your solution is 12345678765432

解释

需要找100万以上的前两个素数，并且其单独的数字总和也是素数。 例如23是质数，数字和5也是质数。

然后拼接起来，提交即可。

Python3

用Python实现：

首先定义个函数， 判断是素数

def is_prime(num):
    for i in range(2, num):
        # 如果能整除num，就说明不是素数
        if num % i == 0 and num != 2:
            return False
    return True

接着开始找这两个素数

list = []
times = 0
now = 1000000

# 找两个数
while times < 2:
        #当前数值是素数
        if is_prime(now):
            #每个数字的和也是 素数
            sums_of_number = sum(map(int, str(now)))
            if is_prime(sums_of_number):
                list.append(now)
                times += 1
        #继续判断下一个数
        now += 1
print(list)

上面对单个数字求和的代码是：

sums_of_number = sum(map(int, str(now)))

这种写法参考了[1][WeChall] Another Python Solution [WeChall]->Solution: Prime Factory

用到了map()函数：

map() 会根据提供的函数对指定序列做映射。
第一个参数 function 以参数序列中的每一个元素调用 function函数，返回包含每次 function 函数返回值的新列表。

其实还有一种写法： 用到了列表推导式

sums_of_number = sum([int(tmp) for tmp in str(now)])

参考了[1][WeChall] a Python3 solution [WeChall]->Solution: Prime Factory

答案

运行代码，结果是：[1000033, 1000037]

拼接后，提交 10000331000037 即可。

C语言

再用C语言来写下：

#include <stdio.h>
int is_prime(int num)
{
    for (int i = 2; i < num; i++)
    {
        if (num % i == 0 && num != 2)
        {
            return 0;
        }
    }
    return 1;
}

int digits_sums(int num)
{
    int sums = 0;
    while (num > 0)
    {
        sums += num % 10;
        num /= 10;
    }
    return sums;
}

int main(void)
{
    int times = 0;
    int now = 1000000;
    while (times < 2)
    {
        if(is_prime(now) && is_prime(digits_sums(now))) {
            printf("%d\n", now);
            times++;
        }
        now ++;
    }

    return 0;
}

PHP

<?php
function is_prime($num)
{
    for ($i  = 2; $i < $num; $i++) {
            if ($num % $i == 0 && $num != 2)

            return false;
    }
    return true;
}

function digits_sums($num){
    $sums = 0;
    while ($num > 0) {
        $sums += $num % 10;
        $num /= 10;
    }
    return $sums;
}

$times = 0;
$now = 1000000;
while ($times < 2) 
{
    if (is_prime($now) && is_prime(digits_sums(($now))))
    {
        printf($now."\n");
        $times ++;
    }
    $now++;
}

?>

其中digits_sums函数还可以借助substr来实现。

function digits_sums($num)
{
    $sums = 0;
    for ($i = 0; $i < strlen($num); $i++) {
        $sums += substr($num, $i, 1);
    }
    return $sums;
}

PHP的写法参考了：

[WeChall] My Solution (PHP) [WeChall]->Solution: Prime Factory
[WeChall] My PHP solution [WeChall]->Solution: Prime Factory

JavaScript

function is_prime(num) {
    for (var i = 2; i < num; i++)
        if (num % i == 0 && num != 2) return false
    return true
}

function digits_sums(num){
    var sums = 0
    while (num > 0)
    {
        sums += num % 10;
        num = parseInt(num/10);
    }
    return sums;
}

var times = 0;
var now = 1000000;
while (times < 2) {
    if (is_prime(now) && is_prime(digits_sums(now))) {
        console.log(now)
        times ++
    }
    now ++
}

Bash

因为在bash中return的返回值不能大于255，所以不能实现类似C语言的digits_sums函数。

注意： 运行时间需要几秒。

#!/bin/bash
function is_prime(){
    for ((i = 2; i < $1; i++))
    do
        if [ $(($1%$i)) -eq 0 ] && [ $1 -ne 2 ]
        then
            return 0 
        fi
    done
    return 1
}

times=0
num=1000000;
while (( $times<2 ))
do
    sum=0
    now=$num
    while(( $now>0 ))
    do
        sum=$(($sum+$now%10))
        now=$(($now/10))
    done

    is_prime $num
    num_is_prime=$?

    is_prime $sum
    sum_is_prime=$?

    if [ $num_is_prime -eq 1 ] && [ $sum_is_prime -eq 1 ]
    then
        echo $num
        times+=1
    fi
    num=$(($num+1))
done

Bash的参考：

Shell 教程 | 菜鸟教程
linux shell bash 比较操作
Shell中if的使用详解_&&与||的使用详解
Shell全局变量、局部变量与特殊变量笔记总结
Linux学习第二十一篇--了解bash Shell(局部变量和全局变量)