题目35：100万以下有多少个循环质数？
本帖最后由 欧拉计划 于 2015-4-24 00:00 编辑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 于 2016-7-9 23:12 编辑
算法不怎么好,仅仅是把题作出来了.耗时85535ms.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>
#define MAXN 1000000 //要修改栈默认大小
struct node{
char str;
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 = stmp;
}
p = '\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,i,j,* pnum,* px;
PNode ph=NULL;
PNode pdx;
char stmp={0};
int start,stop;
//1.num数组赋值1,2,3...
start = (int)GetTickCount();//计时
for(i=0;i<MAXN;i++)
{
num = 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!=0 && num!=1){
//printf("%d,",num);
addnode(&ph,itoa(num,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)
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)+str(i)
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)+str(i)+str(i)
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)+str(i)+str(i)+str(i)
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)+str(i)+str(i)+str(i)+str(i)
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 本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:35 编辑
import math
def zhuanhuan(num):
list1 = []
count = len(str(num))
str1 = str(num)
while count:
list1.append(int(str1 + str1))
str1 = str1 + str1
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))
55
不知道答案对不对，求真相
耗时大概10s,求优化 376103327 发表于 2016-10-26 23:39
import math
def zhuanhuan(num):
list1 = []
优化了一下算法
55
import math
def getprime(n):
primes = *n
primes, primes = False,False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = 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 = * N
l_result, l_result = False, False
for i in range(0, N):
if l_result:
for j in range(i * i, N, i):
l_result = False
return l_result
def euler034(N=1000000):
l_primes = getPrimes(N)
l_k =
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 + tmp
if not l_primes:
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))
55
cost 0.532378 sec
本帖最后由 渡风 于 2017-6-14 21:42 编辑
此代码使用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
ifIscycle(Vector(ii)) == 1
Output = Output + 1;
disp(Vector(ii))
end
end
toc
disp('此代码使用matlab编程')
disp(['Problem35所用时间为： ',num2str(toc),'秒'])
disp(['Problem35的答案为： ',num2str(Output)]) 本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:35 编辑
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+p))
p = p + p
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 import math
import itertools
from time import time
lst1 =
lst4 =
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+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:
lst_f.pop(0)
T = True
elif lst_t != [] and j == lst_t:
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) 本帖最后由 王小召 于 2019-6-13 16:28 编辑
共有循环质数：55个
分别是：
用时：6.3180404999999995 秒
import time
def prime_list(num_range):
bool_num = * (num_range+1)
bool_num = 0
bool_num = 0
for i,j in enumerate(bool_num):
if j:
for x in range(i**2, num_range+1, i):
bool_num = 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] for i in range(len(str(num)))]:
if not bool_nums:
mark = 0
break
if mark == 1:
for each in + 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())) 本帖最后由 永恒的蓝色梦想 于 2020-6-6 09:30 编辑
def func(num):
num=str(num)
for i in range(len(num)-1):
num=num+num
if int(num)not in primeset:
return False
return True
def findprimes(end):
primelist=*(end+1)
primelist=primelist=False
for i,prime in enumerate(primelist[:int(end/2+1)]):
if prime:
for j in range(2*i,end+1,i):primelist=False
return{i for i,prime in enumerate(primelist)if prime}
primeset=findprimes(1000000)
print(sum(func(i) for i in primeset)) 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;
int factor;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
bool isprime(int x){
x = abs(x);
if (x == 0 || x == 1) return false;
for (int i = 1;factor <= sqrt(x);i++)
if (x % factor == 0)return false;
return true;
}
deque<int> dq;
int n;
bool has_zero(){
for (int i = 0;i < dq.size();i++)
if (dq == 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;
//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;
}
#include <stdio.h>
#include <string.h>
#include <math.h>
int tran(int);
int check_num(int);
int tran(int num)
{
char str;
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;
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 /*
答案：55
耗时：0.002754秒
*/
#include <cstdio>
#include <cstring>
using namespace std;
char cPrimes;//素数表
int main(void)
{
//筛法计算素数表
memset(cPrimes, 1, sizeof(cPrimes));
cPrimes = 0;
cPrimes = 0;
for (int i = 2; i < 1000; ++i)
{
if (cPrimes == 0)
continue;
for (int j = i * i; j < 1000000; j += i)
cPrimes = 0;
}
int nCount = 0;
for (int i = 2; i < 1000000; ++i)//穷举各数
{
if (cPrimes == 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 == 0)//检查是否是素数
{
bFind = false;
break;
}
}
if (bFind)
++nCount;//满足要求
}
printf("%d\n", nCount);
return 0;
} #include <vector>
#include <cmath>
#include <iostream>
using namespace std;
bool similar(int x,int y,int len)
{
if(len==1)
return false;
char bits1{0};
char bits2{0};
int i = 0;
while(x>0)
{
bits1 = x%10;
x /= 10;
}
i = 0;
while(y>0)
{
bits2 = y%10;
y /= 10;
}
i = 0;
while(++i<len)
{
for(int j=0;j<len-1;j++)
swap(bits1,bits1);
for(int j=0;j<len;j++)
if(bits1!=bits2)
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);
if(similar(i,i,len+1))
count.back() = -1;
int floornum = pow(10,len);
while(prime[--t]>floornum)
if(similar(i,prime,len+1))
{
count.back() += count;
break;
}
}
i += 2;
}
i = prime.size();
int sum = 0;
for(int j=0;j<i;j++)
{
if(count==-1)
sum ++;
if(count==(int)log10(prime)+1)
sum += count;
}
cout<<sum;
} 一开始看成全排列了，真的难顶啊
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=0
continue
num=2
while i*num<=n:
data=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==0:
break
if not data==0:
aa.append(k)
a=a+1
print(aa)
print(a)
print('Time:{}s'.format(time.time()-st))
页:
[1]