【Codeforces 584D】Dima and Lisa
2024-08-30 22:34:26
【链接】 我是链接,点我呀:)
【题意】
让你把一个奇数n分成最多个质数的和
【题解】
10的9次方以内,任意两个质数之间的差距最大为300
因此可以这样,我们先从i=n-2开始一直递减直到i变成最大的p(p
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = 50000;
static class Task{
boolean is(int x) {
int len = (int)Math.sqrt(x);
for (int i = 2;i <=len;i++)
if (x%i==0)
return false;
return true;
}
int n;
public void solve(InputReader in,PrintWriter out) {
n = in.nextInt();
int len = (int)Math.sqrt(n);
if (is(n)) {
out.println(1);
out.println(n);
return;
}
//n不是质数,n是奇数
for (int i = n-2;i >= 1;i--) {
if (is(i)) {
int rest = n-i;
if (rest==2) {
out.println(2);
out.print(i+" "+rest);
}else {
for (int j = 2;j <= rest;j++) {
if (is(j)&&is(rest-j)) {
out.println(3);
out.print(i+" "+j+" "+(rest-j));
return;
}
}
}
break;
}
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
最新文章
- Android NDK, No rule to make target
- nonatomic, retain,weak,strong用法详解
- 树莓派如何便捷的使用pi4j
- IBM MQ消息中间件jms消息中RHF2消息头的处理
- 【转】uboot移植(一)BootLoader基本概念
- 在老项目中使用Gradle：更改默认目录结构
- windows程序设计读书笔记1——创建窗口
- Qt开发小工具之gif转换器（使用QMovie截取每一帧为QImage，然后用QFile另存为图片文件）
- 复习TextView（查漏补缺）
- Cow Exhibition 变种背包
- yii2-swiftmailer入门
- 图像风格迁移（Pytorch）
- 使用Redis构建全局并发锁
- Apollo 10 — adminService 全量发布
- bash和shell的关系
- Jakarta项目
- 【Java面试题】26 多线程有几种实现方法?同步有几种实现方法? 当一个线程进入一个对象的一个synchronized方法后，其它线程是否可进入此对象的其它方法？
- 解决PHPWind局域网不能访问问题
- 20155325《Java程序设计》实验一（Java开发环境的熟悉）实验报告
- UIControl笔记