题目35：100万以下有多少个循环质数？

欧拉计划

Circular primes

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

题目：

我们称 197 为一个循环质数，因为它的所有轮转形式： 197, 971 和 719 都是质数。

100 以下有 13 个这样的质数： 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和 97.

100 万以下有多少个循环质数？

yundi

算法不怎么好,仅仅是把题作出来了.耗时85535ms.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>

#define MAXN 1000000 //要修改栈默认大小
struct node{
        char str[5];
        int fg;
        struct node * pnext;
} node ;
typedef struct node Node,* PNode;

PNode addnode(PNode * pphead , char * p)
{
        PNode pd;
        if(* pphead == NULL)
        {
                * pphead = (PNode)malloc(sizeof(Node));
                memset(* pphead,0,sizeof(Node));
                strcpy((* pphead)->str,p);
                (* pphead)->pnext = NULL;
        }else{
                pd = * pphead;
                while(pd->pnext != NULL)
                {
                        pd = pd->pnext;
                }
                pd->pnext = (PNode)malloc(sizeof(Node));
                memset(pd->pnext,0,sizeof(Node));
                strcpy(pd->pnext->str,p);
                pd->pnext->pnext = NULL;
        }
        return * pphead;
}

void printnode(PNode phead)
{
        PNode px=phead;
        while(px!=NULL )
        {
                if(px->fg != 0)
                {
                        printf("%p:\t%s\t是循环质素\n",px,px->str);
                }                
                px = px->pnext;
        }
}

int find(char * stmp,PNode phead)
{
        int slen = strlen(stmp);
        int i;
        int fg = 0;
        PNode pd = phead;
        char * p = (char *)malloc(sizeof(char)*(slen+1));
        memset(p,0,sizeof(char)*(slen+1));
        //stmp倒序
        for(i=0;i<slen;i++)
        {
                p[i] = stmp[slen - i - 1];
        }
        p[i] = '\0';
        //在链表中比对
        while(pd!=NULL && strlen(pd->str)<=slen)
        {
                if(strcmp(p,pd->str)==0)
                {
                        pd->fg = 1;
                        fg = 1;
                        break;
                }else{
                        pd = pd->pnext;
                }
        }
        free(p);//用完释放
        return fg;
}
int main()
{
        int num[MAXN],i,j,* pnum,* px;
        PNode ph=NULL;
        PNode pdx;
        char stmp[5]={0};
        int start,stop;

        //1.num数组赋值1,2,3...
        start = (int)GetTickCount();//计时
        for(i=0;i<MAXN;i++)
        {
                num[i] = i+1;                
        }
        //2.num数组中筛选出质数
        pnum = num+1;
        while(pnum <= num + MAXN)
        {
                if(*pnum!=0)
                {
                        px = pnum+(*pnum);
                        while(px<=num+MAXN)
                        {                                
                                * px = 0;
                                px += (*pnum);                                
                        }
                }
                pnum ++;
        }
        //3.将质数转化为字符串,保存到链表
        for(i=0;i<MAXN;i++)
        {
                if(num[i]!=0 && num[i]!=1){
                        //printf("%d,",num[i]);
                        addnode(&ph,itoa(num[i],stmp,10));
                }
        }
        //4.在链表中筛选所需质数
        pdx = ph;
        while(pdx != NULL)
        {
                if(find(pdx->str,ph) == 1)
                {
                        pdx->fg = 1;
                }
                pdx = pdx->pnext;
        }
        stop = (int)GetTickCount();
        //5.输出结果
        printnode(ph);
        printf("\n共历时 %d ms",stop-start);
        //6.释放链表资源,略
    getchar();
}

愤怒的大头菇

import math
def prime(x):
      if x > 1:
            if x == 2:
                  return True
            if x % 2 == 0:
                  return False
            for i in range(3,int(math.sqrt(x))+1,2):
                  if x % i==0:
                        return False
            return True
      return False
list2 = []
for i in range(1,1000000):
      if prime(i):
            for j in range(len(str(i))):
                  if len(str(i)) == 1:
                        if i not in list2:
                              list2.append(i)
                  elif len(str(i)) == 2:
                        list1 = []
                        list1.append(i)
                        Judge = True
                        for n in range(len(str(i))-1):
                              tmp = str(i)[-1] + str(i)[0]
                              list1.append(int(tmp))
                              i = int(tmp)
                        for each in list1:
                              if not prime(each):
                                    Judge = False
                                    break
                        if Judge:
                              if list1 not in list2:
                                    list2.append(list1)
                  elif len(str(i)) == 3:
                        list1 = []
                        list1.append(i)
                        Judge = True
                        for n in range(len(str(i))-1):
                              tmp = str(i)[-1]+str(i)[0]+str(i)[1]
                              list1.append(int(tmp))
                              i = int(tmp)
                        for each in list1:
                              if not prime(each):
                                    Judge = False
                                    break
                        if Judge:
                              if list1 not in list2:
                                    list2.append(list1)                  
                  elif len(str(i)) == 4:
                        list1 = []
                        list1.append(i)
                        Judge = True
                        for n in range(len(str(i))-1):
                              tmp = str(i)[-1]+str(i)[0]+str(i)[1]+str(i)[2]
                              list1.append(int(tmp))
                              i = int(tmp)
                        for each in list1:
                              if not prime(each):
                                    Judge = False
                                    break
                        if Judge:
                              if list1 not in list2:
                                    list2.append(list1)
                  elif len(str(i)) == 5:
                        list1 = []
                        list1.append(i)
                        Judge = True
                        for n in range(len(str(i))-1):
                              tmp = str(i)[-1]+str(i)[0]+str(i)[1]+str(i)[2]+str(i)[3]
                              list1.append(int(tmp))
                              i = int(tmp)
                        for each in list1:
                              if not prime(each):
                                    Judge = False
                                    break
                        if Judge:
                              if list1 not in list2:
                                    list2.append(list1)
                  elif len(str(i)) == 6:
                        list1 = []
                        list1.append(i)
                        Judge = True
                        for n in range(len(str(i))-1):
                              tmp = str(i)[-1]+str(i)[0]+str(i)[1]+str(i)[2]+str(i)[3]+str(i)[4]
                              list1.append(int(tmp))
                              i = int(tmp)
                        for each in list1:
                              if not prime(each):
                                    Judge = False
                                    break
                        if Judge:
                              if list1 not in list2:
                                    list2.append(list1)
list3 = []
for each in list2:
      if type(each) == list:
            for i in each:
                  if i not in list3:
                       list3.append(i)
      else:
            if each not in list3:
                  list3.append(each)
print(len(list3))

结果：55

376103327

import math
def zhuanhuan(num):
    list1 = []
    count = len(str(num))
    str1 = str(num)
    while count:
        list1.append(int(str1[1:] + str1[0]))
        str1 = str1[1:] + str1[0]
        count -= 1
    return list1

def isZhishu(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            #print num, i, num/i
            return False
    else:
        return True


def zhishu(num):
    list = []
    for i in range(2, num):
        for j in range(2, int(math.sqrt(i))+1):
            if i % j == 0:
                break
        else:
            list.append(i)
    return list
def xunhuanzhishu(num):
    listNum = []
    for i in zhishu(num):
        for j in zhuanhuan(i):
            if not isZhishu(j):
                break
        else:
            listNum.append(i)
    return listNum


print xunhuanzhishu(1000000)
print len(xunhuanzhishu(1000000))

[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]
55

不知道答案对不对，求真相
耗时大概10s,求优化

jerryxjr1220

376103327 发表于 2016-10-26 23:39
import math
def zhuanhuan(num):
    list1 = []

优化了一下算法
55
[Finished in 0.9s]

import math
def getprime(n):
        primes = [True]*n
        primes[0], primes[1] = False,False
        for (i, prime) in enumerate(primes):
                if prime:
                        for j in range(i*i,n,i):
                                primes[j] = False
        plist = []
        for (k, trueprime) in enumerate(primes):
                if trueprime:
                        plist.append(k)
        return plist

def iscycle(n):
        l = int(math.log10(n))
        for i in range(l):
                n = (n%10)*(10**l)+n//10
                if isprime(n) == False:
                        return False
        return True

def isprime(n):
        for e in primelist:
                if n%e == 0:
                        return False
                if e*e>n:
                        break
        return True

primelist = getprime(1000000)
count = 0
for each in primelist:
        if iscycle(each):
                count += 1
print (count)

芒果加黄桃

# encoding:utf-8
# 寻找100万以下的循环质数
from time import time
def getPrimes(N=1000000):
    l_result = [True] * N
    l_result[0], l_result[1] = False, False
    for i in range(0, N):
        if l_result[i]:
            for j in range(i * i, N, i):
                l_result[j] = False
    return l_result
def euler034(N=1000000):
    l_primes = getPrimes(N) 
    l_k = [k for (k, v) in enumerate(l_primes) if v]
    l_result = []
    for each in l_k:
        if each in l_result:
            continue
        tmp = str(each)
        if len(tmp) == 1:
            l_result.append(each)
            continue
        else:
            flag = True
            l_tmp = []
            for i in range(1, len(tmp)):
                tmp = tmp[1:] + tmp[0]
                if not l_primes[int(tmp)]:
                    flag = False
                    break
                else:
                    l_tmp.append(int(tmp)) 
            if flag:        
                l_result.append(each)
                l_result.extend(l_tmp)
    l_result = list(set(l_result))
    l_result.sort()
    print(l_result)
    print(len(l_result))
if __name__ == '__main__':
    start = time() 
    euler034(1000000)
    print('cost %.6f sec' % (time() - start))

[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]
55
cost 0.532378 sec

渡风

此代码使用matlab编程
Problem35所用时间为： 44.836秒
Problem35的答案为： 55

%% Problem35.m
% 最后编辑时间：17-06-14 22:00
% 找出100w以下的循环质数
% Problem35所用时间为： 44.836秒
% Problem35的答案为： 55
function Output = Problem35()
tic
Limit = 1000000;
Vector = GetPrime(Limit); 
N = length(Vector);

Output = 0;

for ii = 1:N  
    if  Iscycle(Vector(ii)) == 1
        Output = Output + 1;
        disp(Vector(ii))
    end
end

toc
disp('此代码使用matlab编程')
disp(['Problem35所用时间为： ',num2str(toc),'秒'])
disp(['Problem35的答案为： ',num2str(Output)])

Trami

import numpy as np
import time

stime = time.time()

def prime(n):
    if n <= 1:
      return False
    for i in range(2, int(np.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def prod_digit(x):
    result = []
    p = str(x)
    count = len(p)
    str1 = str(x)
    while count:
        result.append(int(p[1:]+p[0]))
        p = p[1:] + p[0]
        count -= 1
    return result

result = []
temp = []
for i in range(0, 1000000):
    if prime(i):
        a = prod_digit(i)
        for item in a:
            temp.append(prime(item))
        if False not in temp:
            result.append(i)
        temp = []
print(len(result))

end = time.time()

print(end - stime)

运行26s

JAY饭

import math
import itertools
from time import time

lst1 = [2,3]
lst4 = [2,3]
lst_t = []
lst_f = []

def zhi1(n):
    if n%2 == 0: return False
    else:
        for i in lst1:
            if i > math.sqrt(n):
                break
            if n%i == 0:
                return False
        if n <1000:
            lst1.append(n)
        return True

def zhi2(n):

    if n%2 == 0: return False
    else:
        for i in lst1:
            if i > math.sqrt(n):
                break
            if n%i == 0:
                return False
        return True

for i in range(5,1000):
    zhi1(i)
    
def text(a):
    while a<1000000:
        if zhi2(a):
            yield a
        a += 2

def pailie(number):
    lst2 = []
    while number:
        if number < 10:
            lst2.insert(0,number)
        else:
            s = number%10
            lst2.insert(0,s)
        number //= 10
    return lst2

def ite(lst2):
    lst3 = set()
    for k in lst2:
        if k%2 == 0:
            return False
    for i in range(len(lst2)):
        temp = lst2[i+1:]+lst2[:i+1]
        m = ''
        for j in temp:
            m += str(j)
        lst3.add(int(m))
    return list(lst3)

def shengcheng():
    a = 0
    final = set()
    for i in text(5):
        if i:
            itr = ite(pailie(i))
            if itr:
                F,T = True,False
                for j in itr:
                    if lst_f != [] and j == lst_f[0]:
                        lst_f.pop(0)
                        T = True
                    elif lst_t != [] and j == lst_t[0]:
                        a += 1
                        lst_t.pop(0)
                        final.add(i)
                        T = True
                if T:
                    continue
                lst_m = []
                for j in itr:
                    if zhi2(j):
                        lst_m.append(j)
                    else:
                        F = False
                if not F:
                    for j in lst_m:
                        if j > i:
                            lst_f.append(j)
                if F:
                    final.add(i)
                    a += 1
                    for j in lst_m:
                        if j > i:
                            lst_t.append(j)
                lst_f.sort()
                lst_t.sort()
    print(len(final))

start = time()
shengcheng()
print('消耗%.2f'%(time()-start))
##print(lst_t)
##print(lst_f)

王小召

共有循环质数：55个
分别是：[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]
用时：6.3180404999999995 秒

import time

def prime_list(num_range):
    bool_num = [1] * (num_range+1)
    bool_num[0] = 0
    bool_num[1] = 0
    for i,j in enumerate(bool_num):
        if j:
            for x in range(i**2, num_range+1, i):
                bool_num[x] = 0
    return bool_num

def cal_result(X_range):
    bool_nums = prime_list(X_range)
    result = []
    for num in range(2, X_range):
        if num in result:
            continue
        else:
            mark = 1
            for each_value in [str(num)[i:] + str(num)[:i] for i in range(len(str(num)))]:
                if not bool_nums[int("".join(each_value))]:
                    mark = 0
                    break
            if mark == 1:
                for each in [str(num)[i:] + str(num)[:i] for i in range(len(str(num)))]:
                    result.append(int(each))
    return list(set(result))

result = cal_result(1000000)
result.sort()
print("共有循环质数：{}个\n分别是：{}\n用时：{} 秒".format(len(result), result, time.process_time()))

永恒的蓝色梦想

def func(num):
  num=str(num)
  
  for i in range(len(num)-1):
    num=num[1:]+num[0]
    
    if int(num)not in primeset:
        return False
    
  return True


def findprimes(end):
  primelist=[True]*(end+1)
  primelist[0]=primelist[1]=False
  
  for i,prime in enumerate(primelist[:int(end/2+1)]):
    if prime:
      for j in range(2*i,end+1,i):primelist[j]=False
      
  return{i for i,prime in enumerate(primelist)if prime}


primeset=findprimes(1000000)
print(sum(func(i) for i in primeset))

debuggerzh

55

Process returned 0 (0x0)   execution time : 0.828 s
Press any key to continue.
使用STL容器deque，欧拉筛打表，注意到数字不能出现0

#include<iostream>
#include<cmath>
#include<cstring>
#include<deque>
using namespace std;

const int M = 1e6;
int cnt = 0;
bool prime[M];
int factor[M];

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) factor[++cnt] = i;
    for (int j = 1;j <= cnt && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

bool isprime(int x){
  x = abs(x);
  if (x == 0 || x == 1) return false;
  for (int i = 1;factor[i] <= sqrt(x);i++)
    if (x % factor[i] == 0)  return false;
  return true;
}

deque<int> dq;
int n;

bool has_zero(){
  for (int i = 0;i < dq.size();i++)
    if (dq[i] == 0) return true;
  return false;
}

bool cir_prime(int x){
  if (!isprime(x))  return false;
  dq.clear();

  while(x){
    dq.push_front(x % 10);
    x /= 10;
  }
  if (has_zero()) return false;
  dq.push_back(dq.front());
  dq.pop_front();

  int t = 0;
  for (int i = 0;i < dq.size();i++)
    t = t * 10 + dq[i];
  //cout << t << endl;
  if (t == n) return true;
  return cir_prime(t);
}

int main(){
  euler_sieve();
  int cnt = 1;//把2先算上

  for (n = 3;n < M;n+=2){
    dq.clear();
    if (cir_prime(n)) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

a1351468657

#include <stdio.h>
#include <string.h>
#include <math.h>

int tran(int);
int check_num(int);

int tran(int num)
{
        char str[10];
        int i, j, k;
        k = num;
        j = k % 10;
        k /= 10;
        
        sprintf(str, "%d", k);
        i = strlen(str);

        k += j * pow(10, i);
        return k;
}

int check_num(int num)
{
        int i, j, k;
        k = num;
        j = sqrt(num + 1);
        for (i = 2; i <= j; i++)
        {
                if (k % i == 0)
                {
                        return 0;
                }
        }
        return 1;
}

main()
{
        char str[32];
        int i, j, len, flag = 1;
        int count = 13; //100以下有13个质数

        for (i = 100; i < 1000000; i++)
        {
                sprintf(str, "%d", i);
                len = strlen(str);
                j = i;
                while (len)
                {
                        if (check_num(j))
                        {
                                j = tran(j);
                        }
                        else
                        {
                                flag = 0;
                                break;
                        }
                        len--;
                }
                if (flag)
                {
                        printf("%d ", i);
                        count++;
                }
                flag = 1;
        }
        printf("\n%d\n", count);
}

100万以内一共有55个循环质数
113 131 197 199 311 337 373 719 733 919 971 991 1193 1931 3119 3779 7793 7937 9311 9377 11939 19391 19937 37199 39119 71993 91193 93719 93911 99371 193939 199933 319993 331999 391939 393919 919393 933199 939193 939391 993319 999331

guosl

/*
答案：55
耗时：0.002754秒
*/
#include <cstdio>
#include <cstring>
using namespace std;

char cPrimes[1000000];//素数表

int main(void)
{
  //筛法计算素数表
  memset(cPrimes, 1, sizeof(cPrimes));
  cPrimes[0] = 0;
  cPrimes[1] = 0;
  for (int i = 2; i < 1000; ++i)
  {
    if (cPrimes[i] == 0)
      continue;
    for (int j = i * i; j < 1000000; j += i)
      cPrimes[j] = 0;
  }
  int nCount = 0;
  for (int i = 2; i < 1000000; ++i)//穷举各数
  {
    if (cPrimes[i] == 0)
      continue;
    int p = i, nLen = 0;
    while (p > 0) //计算这个数的位数
    {
      ++nLen;
      p /= 10;
    }
    p = 1;
    for (int k = 1; k < nLen; ++k)//计算循环中用到的10^(nLen-1)
      p *= 10;
    int j = i;//记录循环数
    bool bFind = true;
    for (int k = 1; k < nLen; ++k)//枚举循环数
    {
      j = j / 10 + (j % 10) * p;//计算循环后的数
      if (cPrimes[j] == 0)//检查是否是素数
      {
        bFind = false;
        break;
      }
    }
    if (bFind)
      ++nCount;//满足要求
  }
  printf("%d\n", nCount);
  return 0;
}

mathtimes

#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
bool similar(int x,int y,int len)
{
    if(len==1)
        return false;
    char bits1[len]{0};
    char bits2[len]{0};
    int i = 0;
    while(x>0)
    {
        bits1[i++] = x%10;
        x /= 10;
    }
    i = 0;
    while(y>0)
    {
        bits2[i++] = y%10;
        y /= 10;
    }
    i = 0;
    while(++i<len)
    {
        for(int j=0;j<len-1;j++)
            swap(bits1[j],bits1[j+1]);
        for(int j=0;j<len;j++)
            if(bits1[j]!=bits2[j])
                goto continuetodo;
        return true;
        continuetodo:;
    }
    return false;
}
int main()
{
    vector<int> prime,count;
    prime.reserve(73000);
    count.reserve(73000);
    prime.push_back(2);
    count.push_back(1);
    int i = 3;
    while(i<(int)1e6)
    {
        bool s = true;
        for(auto j=prime.begin();*j<=sqrt(i)&&j!=prime.end();j++)
            if(i%*j==0)
            {    
                s = false;
                break;
            }
        if(s)
        {
            prime.push_back(i);
            count.push_back(1);
            int t = prime.size()-1;
            int len = (int)log10(prime[t]);
            if(similar(i,i,len+1))
                count.back() = -1;
            int floornum = pow(10,len);
            while(prime[--t]>floornum)
                if(similar(i,prime[t],len+1))
                {
                    count.back() += count[t];
                    break;
                }
        }
        i += 2;
    }
    i = prime.size();
    int sum = 0;
    for(int j=0;j<i;j++)
    {
        if(count[j]==-1)
            sum ++;
        if(count[j]==(int)log10(prime[j])+1)
            sum += count[j];
    }
    cout<<sum;
}

TLM

一开始看成全排列了，真的难顶啊
[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]
55
Time:2.2769715785980225s

import time
st=time.time()
nn=6
n=10**nn
aa=[]
a=0
data=list(range(n+1))
for i in range(int(n**0.5)+1):
    if i<=1:
        data[i]=0
        continue
    num=2
    while i*num<=n:
        data[i*num]=0
        num=num+1
# print(data[:20:])
for k in data:
    if k==0:
        continue
    ii=k
    l=[]
    while ii>0:
        l.append(ii%10)
        ii=ii//10
    for i in range(len(l)):
        num=0
        for j in range(len(l)-1,-1,-1):
            num=num*10+l[(i+j)%len(l)]
        if data[num]==0:
            break
    if not data[num]==0:
        aa.append(k)
        a=a+1
    
print(aa)
print(a)
print('Time:{}s'.format(time.time()-st))