看板java
標 題Re: [問題] 找出第幾個質數
發信站SayYA 資訊站 (Thu Jun 1 11:31:30 2006)
轉信站ptt!ctu-reader!news.nctu!SayYa
※ 引述《[email protected] (BER)》之銘言：
> import java.util.Scanner;
> public class DD{
> public static void main(String[] args){
> Scanner scanner = new Scanner(System.in);
> System.out.print("請輸入測試的數字:");
> int d =scanner.nextInt();
> int x=d;
> int i,y,count=3;
> int[] arr =new int[100];
> for(int ar=0;ar<100;ar++)
> arr[ar]=ar;
> arr[1]=2;
> arr[2]=3;
> for(i=5;i<x;i++)
> {
> for(y=2;y<i;y++)
> {
> if ((i%y)==0)
> break;
> }
> if((i%y)!=0) {
> arr[count]=i;
> count++;
> }
> }
> for(int z=1;z<100;z++)
> {
> if(arr[z]==x)
> System.out.println(z);
> }
> } }
> 這個程式是輸入一個數字判斷他是第幾個質數
> 但是我找不出我哪個有問題..
1. 您沒有質數表
2. 您也沒說您有什麼問題
建議改善的方法:
使用Sieve of Eratosthenes質數演算方式
先列出2~x的所有數列(可以存在list中)
由第一項(A1)開始(也就是2，是一個質數)到第An項，也就是值為x那一項
用第i項去除餘所有i+1, i+2...n的項目，可以整除的都不是質數(不是的刪掉)
第i項檢查完畢，再由i+1項去除餘i+2, i+3...n
最後，如果你輸入的x是質數(不是的早被刪掉了)
那x在那一項就是第幾個了
--
※ Origin: SayYA 資訊站 <bbs.sayya.org>
◆ From: 163.26.34.214