討論 - 有關質數

[clout]

現在有個問題，印出小於60的質數

但有公式能算出質數嗎?或是有什麼其他辦法??

麻煩請各位給我一個方向，在邏輯上該怎麼想

除了1與自己外，沒其他因數，然後......?

[猜謎人]

你可以做巢狀循環
兩個for
第一個從1到60
每一個數字從1一直除到他本身，這是第二個for
只有1和他本身可以整除就列出

[mini]

如猜謎人所言
要設一個計數器 a
For VB

Private Sub Command1_Click()
Dim prime_number(1 To 60) As Boolean
Dim i As Integer, j As Integer, a As Integer

For i = 1 To 60
    a = 0
    For j = 1 To i
        If (i Mod j) = 0 Then a = a + 1
        If a >= 3 Then Exit For
    Next
    If a <= 2 Then prime_number(i) = True
Next

For i = 1 To 60
    If prime_number(i) = True Then Print i
Next

End Sub

[clout]

謝謝兩位

雖然還看不大懂，但至少知道要往哪個方向去想了

[joebin]

作者: clout

謝謝兩位

雖然還看不大懂，但至少知道要往哪個方向去想了

那我用學生的語言解說好了^^"



首先要質數的定義是:
除了自己和1外無其他的因數(1除外)


再來是談論到因數問題:
若正整數N在根號N中只找到1這個因數,則N為質數(1除外)

原因:
設N.n.m為一自然數,且n * m = N,則n.m為N的因數(註:n >= m)
另設一數k,使其 k * k = N,則就n.m.k的大小而言,n >= k >= m
既然n * m = N,且k * k = N,那在小於或等於k的自然數中必能找到m
所以~若正整數N在根號N中只找到1這個因數,則N為質數(1除外)


由此想法來建構一程式

#include<iostream>
using namespace std;
int main(){
  int i,n,N,t;
  cin >>N;     //輸入你所要求質數的最高上限數,例如樓主所發問的60
  for(n=2;n<=N;n++){
    t=1;    //判斷n是否在2~根號n中尚有其他因數存在
    for(i=2;i*i<=n;i++)//若正整數n在根號n中只找到1這個因數,則n為質數
      if(n%i==0){
        t=0;
        break;
    }
    if(t==1) cout <<n<<endl;
  }
  return 0;
}

不知這樣的解說夠不夠清晰^^"

[clout]

請問為什麼寫出來後變成從2印到60@@?

public class zxc{
	public static void main(String[] args){
	
	int i,n,max=0;
	
	System.out.println("質數有");
	for(i=2;i<=60;i++){
	   for(n=2;n<=i;n++){
	       if(i==n && i%n==0){            //兩數相等而已餘數相等，開始執行
	       System.out.println(i);
	       max=i;
	       } 
           }
	}
	System.out.println("最大質數"+max);
}
}

[猜謎人]

public class zxc{
public static void main(String[] args){

int i,n,max=0;

System.out.println("質數有");
for(i=2;i<=60;i++){
for(n=2;n<=i;n++){
if(i==n && i%n==0){ //自己除自己當然可以整除
System.out.println(i);
max=i;
}
}
}
System.out.println("最大質數"+max);
}
}