【九度OJ】题目1163：素数解题报告

2019-11-06 06:05:29

字体：大中小

来源：转载

供稿：网友

【九度OJ】题目1163：素数解题报告

标签（空格分隔）：九度OJ

原题地址：http://ac.jobdu.com/PRoblem.php?pid=1163

题目描述：

输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。

输入：

输入有多组数据。每组一行，输入n。

输出：

输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。

样例输入：

100

样例输出：

11 31 41 61 71

Ways

BigInteger类！

这个类中含有nextBigInteger()方法可以获得这个数的下一个素数，因此可以据此判断。刚开始的代码有PE错误，原因是每行的末尾有多余空格。下面是正确代码。

import java.util.*;import java.math.*;public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { BigInteger in = scanner.nextBigInteger(); boolean exit = false;//作为是否存在以及换行的标志 BigInteger x = new BigInteger("10"); while (x.compareTo(in) < 0) {//小于10的数直接输出-1 if (x.remainder(new BigInteger("10")).intValue() == 1) {//位数是否为1 if(!exit){ System.out.printf("%d", x.intValue()); }else{ System.out.printf(" %d", x.intValue()); } exit = true; } x = x.nextProbablePrime();//下一个素数 } if (exit) { System.out.print("/n"); } else { System.out.println("-1"); } } }}

感觉可以更加优化，不用每个数都进行遍历进行判断。想法是每次把数字加10，判断此后的数字是或否为素数。感觉和上面方法差别不大，所以我就用C++代码实现了。

#include <stdio.h>#include <math.h>bool isPrime(int n) { for (int i = 2; i <= (int) sqrt(n) + 1; i++) { if (n % i == 0) { return false; } } return true;//是否为素数，别弄反}int main() { int n; while (scanf("%d", &n) != EOF) { if (n <= 11) {//这里保证11这个数输入进来的时候不会输出 printf("-1/n"); } else { bool exit = false; for (int i = 11; i < n; i += 10) {//从11开始判断 if (isPrime(i)) { if (!exit) { printf("%d", i); exit = true; } else { printf(" %d", i); } } } if (exit) { printf("/n"); } else { printf("-1/n"); } } } return 0;}