应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三十五题：循环质数
41/1返回列表
查看: 1691  |  回复: 16
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 4 个 程序强帖 ，点击这里进行查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-07-07 14:43:53
余泽成(金币+2, 程序强帖+1): 鼓励交流！ 2011-07-11 20:35:50
c++的效率还是高
不过初学c++,谁知道还有什么数字,字符串转换的高效方法吗?
第二个子函数中计算rotation number的办法好丑陋
CODE:
#include
using namespace std;

// 素数筛: 返回0-stop的数组,素数位置为1,其余位置为0
// 从第一个非素数开始,直到大于stop的平方根
// 方法是挨着划去当前数的倍数
int *primes(int stop)
{
    int *numlist = new int[stop+1];
    int i;

    for(i=0;i<=stop;++i)
    {
        if(i<2)
            numlist[i] = 0;
        else
            numlist[i] = i;
    }

    i = 2;
    while(i*i<=stop)
    {
        if(numlist[i]>0)
        {
            for(int j=i+1;j<=stop;++j)
                if(numlist[j]%i==0)
                    numlist[j] = 0;
        }
        i++;
    }

    return numlist;
}

// 判断所有循环是否都是素数
bool checkRotation(int n, int *pmlist)
{
    bool flag = true;
    if(n<10) return flag; // 小于10,直接返回true

    char strnum[7] = ""; // <=1,000,000,7位就够
    sprintf(strnum,"%d",n); // 转为字符串

    int len = strlen(strnum); // 长度
    int curNum,i,j;

    char sNewNum[7] = ""; // 旋转数的字符串形式

    for(i=1;i     {
        // 从位置i开始的旋转数
        for(j=0;j         {
            if(i+j                 sNewNum[j] = strnum[i+j];
            else
                sNewNum[j] = strnum[i+j-len];
        }

        sscanf(sNewNum,"%d",&curNum); // 转为数字
        //cout<
        // 判断是否是素数
        if(pmlist[curNum]==0)
        {
            flag = false;
            break;
        }
    }

    return flag;
}

// euler35
int main(int args, char* argv[])
{
    int stop = 1000000;
    int i,num = 0;
    int *pmlist = primes(stop);

    for(i=0;i<=stop;++i)
        if(pmlist[i]>0 && checkRotation(i,pmlist))
            num++;

    cout<<"小于 "<     return 0;
}

结果
CODE:
//小于 1000000 满足条件的数有: 55 个.
//Process returned 0 (0x0)   execution time : 1.703 s
//Press any key to continue.
赞一下(3人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
4楼2011-07-07 03:10:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
dubo(金币+1): 欢迎常来程序语言版讨论 2011-07-07 14:44:00
余泽成(金币+2, 程序强帖+1): 鼓励交流！ 2011-07-11 20:36:23
算法好的话，python也不慢
CODE:
# Euler Project Problem 35
#

# Gen a prime list
oneMillion = 1000000
primes = range(2, oneMillion+1);

for x in primes:
    if x > 0:
        for n in xrange(2*x, oneMillion+1, x):
            primes[n-2] = 0

primes = [x for x in primes if x > 0]


primes = set(primes)
# Count
count = 0
for n in primes:
    s = str(n)
    flag = True
    for x in xrange(len(s)):
        s = s[1:] + s[0]
        if int(s) not in primes:
            flag = False
            break
    if flag:
        count += 1
        print n
print "Total", count

引用回帖:
Total 55

real        0m1.244s
user        0m1.200s
sys        0m0.040s
赞一下(2人) 回复此楼
5楼2011-07-07 09:11:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-07-07 14:44:14
余泽成(金币+2, 程序强帖+1): 鼓励交流！ 2011-07-11 20:37:14
=w=竟然热感冒了，那么就放下手头工作，来玩一下吧~~
CODE:
#include

#define MAXNUM 1000000

unsigned char notPrime[MAXNUM];
int prime[100000]; //素数个数的估计方法：pi(x) ~ x / ln(x)

int main(){
    int i, j, countPrime;
    int digits, nextBase, currentBase;
    int temp;
    int total=0; //最终结果的计数器

    for(i=2; i         if(notPrime[i]) continue;
        for(j=i+i; j             notPrime[j] = 1;
        }
    } //筛法求素数表

    for(countPrime=0, i=2; i         if(!notPrime[i]){
            prime[countPrime] = i;
            countPrime ++;
        }
    } //把素数放到数组中

    digits = 1;
    currentBase = 1;
    nextBase = 10;
    for(i=0; i         temp = prime[i];

        if(temp/nextBase>0){
            digits++;
            currentBase = nextBase;
            nextBase *= 10;
        } //判定当前十进制数的位数

        for(j=1; j             temp = temp/10 + (temp%10)*currentBase; //把个位数放到最高位
            if(notPrime[temp]) break;
        }

        if(j==digits) total++; //如果循环数都能通过测试
    }

    printf("Total = %d\n", total);

    return 0;
}
赞一下(3人) 回复此楼
7楼2011-07-07 10:27:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
xzhdty(金币+1): 欢迎常来程序语言版讨论 2011-07-07 19:51:23
余泽成(金币+2, 程序强帖+1): 很全面！ 2011-07-11 20:34:48
引用回帖:
Originally posted by libralibra at 2011-07-07 14:50:40:
多谢指教哦,我刚开始看c++,c也忘记的差不多了,还得多学习.感觉c和c++的那些个函数,库晕晕乎乎分不清楚,

那些库很容易分的啦，规则有三：
C++标准库都是不带.h的，如
C++继承C标准库是带C头的，比较容易弄混的就是这两个了：，前面的那个是c版本的，后面那个是string类
C++的头文件可以是hpp，据说是h+cpp的意思，这个多半是模板，因为模板需要编译时实例化，实现代码也在头文件里面
C和C++的操作在某些方面不同，主要有：
a.IO库是不能混合用的，他们之间不存在共享或者同步关系，scanf/printf和istream/ostream要分开使用
b.C没有名字空间，而C++有，于是C里面的一些struct被封装到了std里面，比如struct tm，C++里面它是一个类，并且引用它需要打开名字空间std
c.C的字符串处理统统集中在了string.h里面，字符串是char*和const char*，字符串的IO应该使用sscanf/sprintf，而C++的字符串处理集中在了string类中，这意味着C++使用字符串都应该用string而非char *，字符串的IO则应该使用stringstream，不过上述做法在某些时候有性能问题，操作起来很费事又挨批。
d.C没有而C++有的一个就是容器库和算法库，C的数据法宝是指针+结构体+数组，C++的数据法宝则是迭代器+类+容器，C++的容器库跟算法库对接很麻烦，迭代器固然是好东西，别人实现的拿过来就用着爽，自己实现接口就想骂人，哎……
再多的也说不上了，反正C++用起来就是很麻烦，天生麻烦，纯种没杂种优势啊，看起来好看，难养活。
赞一下(3人) 回复此楼
漩涡的中心有一块空地，空空的。
16楼2011-07-07 16:09:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
41/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭