POJ - 2262 - Goldbach's Conjecture（筛选素数）

男娘i 2022-06-08 11:20 98阅读 0赞

给出一个数字，然后用两个素数的和来表示这个数n；

先筛选素数，打表，然后遍历，从3开始，**每次加2**，因为偶数一定不是素数；

然后用n减去i，去判定是不是素数，不需要枚举；

#include<iostream>
    #include<cstring>
    #include<cmath>
    #define MAXN 1000005
    
    using namespace std;
    
    bool isprime[MAXN];
    
    void checkprime(int n) {
       //快速打表
        memset(isprime, true, sizeof(isprime));
        isprime[1] = false;//把1筛除
        for(int i = 3; i <= n; i+=2) {
            if(isprime[i]) {
                for(int j=i+i; j <= n; j+=i) {
       //筛除以i为倍数的数字（一定不是素数）
                    isprime[j] = false;
                }
            }
        }
    }
    
    int main () {
        int n;
        checkprime(MAXN);
        while(cin >> n && n) {
            int m = n, flag = 1;
            for(int i = 3; i <= m; i+=2) {
       //遍历，注意i+=2
                if(isprime[i] && isprime[n-i]) {
                    printf("%d = %d + %d\n", n, i, n-i);
                    flag = 0;
                    break;
                }
            }
            if(flag) puts("Goldbach's conjecture is wrong.");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，98人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hdu 4715 Difference Between Primes (2013网络赛 warm up) & LightOJ 1259 Goldbach`s Conjecture(素数和差)

和以前做过的一题很像，于是没细想就忽略了n==2这种情况。。。。以后不能再手残贡献WA了。。 Hdu 4715 Difference Between Primes 题

川长思鸟来/ 2022年10月31日 13:34/ 0 赞/ 91 阅读

相关 Problem 46 Goldbach's other conjecture （暴力...）

Goldbach's other conjecture Problem 46 It was proposed by Christian Goldbach that

Myth丶恋晨/ 2022年07月15日 03:22/ 0 赞/ 107 阅读

相关 POJ - 2262 - Goldbach's Conjecture（筛选素数）

给出一个数字，然后用两个素数的和来表示这个数n；先筛选素数，打表，然后遍历，从3开始，每次加2，因为偶数一定不是素数；然后用n减去i，去判定是不是素数，不需要枚举；

男娘i/ 2022年06月08日 11:20/ 0 赞/ 99 阅读

相关线性筛选素数

/ @author liu / public class Main{ public static void main(String[] args) { final

男娘i/ 2022年06月02日 03:06/ 0 赞/ 175 阅读

相关 POJ - 2262 Goldbach's Conjecture

Goldbach's Conjecture Description In 1742, Ch

深碍√TFBOYSˉ_/ 2022年05月19日 02:19/ 0 赞/ 84 阅读

相关算法：素数筛选

include <stdio.h> include <stdlib.h> int main(void) { //这个是输出1000以内的

Love The Way You Lie/ 2022年03月20日 15:58/ 0 赞/ 264 阅读

相关素数筛选高效算法

用普通的筛法，1000 0000 的数，需要用时1600ms左右。 include <stdio.h> include <string.h> incl

妖狐艹你老母/ 2021年11月02日 14:32/ 0 赞/ 343 阅读

相关 F - Goldbach`s Conjecture LightOJ - 1259(素数筛）

F - Goldbach\`s Conjecture LightOJ - 1259 题目链接：[https://vjudge.net/contest/70017\prob

迷南。/ 2021年10月29日 07:42/ 0 赞/ 222 阅读

相关 A - Goldbach's Conjecture

A - Goldbach's Conjecture <table> <tbody> <tr> <td><b>Time Limit:</b> 1000MS</

妖狐艹你老母/ 2021年10月23日 12:01/ 0 赞/ 210 阅读

相关 HDU - 1397 - Goldbach s Conjecture 【数论】题解

目录 1.题目 2.代码 1.题目 Goldbach’s Conjecture: For any even

偏执的太偏执、/ 2021年07月24日 12:11/ 0 赞/ 271 阅读