【九度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;}