in các số nguyên tố trong dãy (2 người xem)

[ducshogun]

cho em hỏi nhờ với ạ. em có 1 đề bài.
cho số n hãy in ra tất cả các số nguyên tố từ 1 tới n.

 

[ndu96081631]

cho em hỏi nhờ với ạ. em có 1 đề bài.
cho số n hãy in ra tất cả các số nguyên tố từ 1 tới n.

Cơ bản chứ có phải khó khăn gì đâu bạn

 

[ducshogun]

Cơ bản chứ có phải khó khăn gì đâu bạn

cho em xin code dc không anh

Bài đã được tự động gộp: 13/3/20

Cơ bản chứ có phải khó khăn gì đâu bạn

em mới học nên đang gặp khó khăn, anh cho em xem tham khảo dc không

 

[ndu96081631]

cho em xin code dc không anh

Bài đã được tự động gộp: 13/3/20

em mới học nên đang gặp khó khăn, anh cho em xem tham khảo dc không

Bài tập thì bạn cứ làm đi, xong gửi lên đây mọi người sẽ sửa nếu sai

 

[VetMini]

Đây là bài toán mà quý vị Thầy/Cô dạy lập trình rất khoái ra.
Tuy nhiên, bảo mấy ngôn ngữ như Pascal, C thì còn có lý. VBA là lập trình ứng dụng, học cái này chả có ích lợi gì cả.

Gợi ý:
Bài này có 3 cách giải theo trình độ cao dần. Cách 1 là xét tất cả các số. Cách 2 là chỉ xét số lẻ (số chẵn chỉ có 2 là nguyên tố). Cách 3 là giữ lại mảng kết quả để làm toán chia.

 

[ducshogun]

Đây là bài toán mà quý vị Thầy/Cô dạy lập trình rất khoái ra.
Tuy nhiên, bảo mấy ngôn ngữ như Pascal, C thì còn có lý. VBA là lập trình ứng dụng, học cái này chả có ích lợi gì cả.

Gợi ý:
Bài này có 3 cách giải theo trình độ cao dần. Cách 1 là xét tất cả các số. Cách 2 là chỉ xét số lẻ (số chẵn chỉ có 2 là nguyên tố). Cách 3 là giữ lại mảng kết quả để làm toán chia.

vâng a. đây em làm cho quen thôi anh

 

[VetMini]

vâng a. đây em làm cho quen thôi anh

Quen cái gì? quen tập code hay quen xin code?
Người ta ta gợi ý cho thì cứ code đi rồi nhờ sửa.

 

[Phuocam]

Cách 2 là chỉ xét số lẻ (số chẵn chỉ có 2 là nguyên tố). Cách 3 là giữ lại mảng kết quả để làm toán chia.

Anh có thể gợi ý mẫu cách 3?

 

[HieuCD]

Anh có thể gợi ý mẫu cách 3?

Cứ viết là ra, cần gì mẫu. Chạy lẹ

 

[VetMini]

Anh có thể gợi ý mẫu cách 3?

Theo cách thông thường thì bạn thử chia từ 2 đến N-1. Cứ chia chẵn là không phải số nguyên tố
Cách cải tiến hơn thì chỉ thử chia tới căn 2 của N (căn bản toán, đừng bảo tôi gải thích tại sao nghen )
Cải tiến chút nữa xét N chẵn lẻ ngày từ đầu, và như vậy thì lúc thử chỉ cần chọn số lẻ. For i = 3 To Căn2N step 2
Cải tiến chút nữa (cách 3) thì từ 1 đến N, cứ tìm được 1 số nguyên tố thì giữ nó vào một mảng. Sau đó lúc thử chia thì chỉ chia các số trong mảng này. Tức là khi thử số nguyên tố N thì chỉ cần thử chia cho các số nguyên tố nhỏ hơn hay bằng căn hai N. Thuật toán này hình như gọi là thuật toán sàng lọc thì phải.

 

[snow25]

cho em hỏi nhờ với ạ. em có 1 đề bài.
cho số n hãy in ra tất cả các số nguyên tố từ 1 tới n.

Thử cái code ngu ngu này xem nào.

Function layso(ByVal so As Long) As Variant
     Dim i As Long, a As Long, kq() As String, dk As Boolean, j As Long
         dk = True
         If so = 1 Then
            ReDim kq(1 To 1)
            kq(1) = 1
         Else
            ReDim Preserve kq(1 To 1)
            kq(1) = 1
            a = 1
            For i = 2 To so
                For j = 2 To a
                    dk = True
                    If i Mod kq(j) = 0 Then
                       dk = False
                       Exit For
                    End If
               Next j
                   If dk = True Then
                      a = a + 1
                      ReDim Preserve kq(1 To a)
                      kq(a) = i
                   End If
          Next i
       End If
       layso = kq()
End Function

 

[Phuocam]

Chỉ làm được cách 2, haha

Public Function InSoNguyenTo(num As Long) As String
Dim temp As String
Dim i As Long
Dim ii As Long
Dim i2 As Long
If num < 2 Then Exit Function
temp = "2"
For i = 3 To num Step 2
    i2 = Sqr(i)
    For ii = 3 To i2 Step 2
        If i Mod ii = 0 Then Exit For
    Next
    If ii > i2 Then temp = temp & ", " & i
Next
InSoNguyenTo = temp
End Function

 

[VetMini]

Con toán tính chia chẵn là:
(n \ m)*m = n
Thường thì hiệu quả hơn Mod.

 

[HieuCD]

Chỉ làm được cách 2, haha

Public Function InSoNguyenTo(num As Long) As String
Dim temp As String
Dim i As Long
Dim ii As Long
Dim i2 As Long
If num < 2 Then Exit Function
temp = "2"
For i = 3 To num Step 2
    i2 = Sqr(i)
    For ii = 3 To i2 Step 2
        If i Mod ii = 0 Then Exit For
    Next
    If ii > i2 Then temp = temp & ", " & i
Next
InSoNguyenTo = temp
End Function

Dùng Mảng kết quả sẽ được cách 3

 

[HieuCD]

Con toán tính chia chẵn là:
(n \ m)*m = n
Thường thì hiệu quả hơn Mod.

Thử rồi, chạy chậm hơn dùng Mod

 

[Phuocam]

..... .

 

[HieuCD]

Làm theo cách 3

Sub XYZ()
  Dim i&, r&, k&, iMax&, Res() As Long
  Const N As Long = 1000000 'So lon nhat

  If N > 1000000 Then k = N / 10 Else k = 100000
  ReDim Res(1 To k, 1 To 1)
  For i = 1 To 3
    If i > N Then Exit For
    Res(i, 1) = i
  Next i
  k = i - 1
  For i = 5 To N Step 2
    iMax = Sqr(i)
    For r = 3 To k
      If Res(r, 1) > iMax Then Exit For
      If (i Mod Res(r, 1)) = 0 Then Exit For
    Next r
    If Res(r, 1) > iMax Then
      k = k + 1
      Res(k, 1) = i
    End If
  Next i
  If k Then Range("A2").Resize(k) = Res
End Sub

 

[VetMini]

Function daySNT(num As Long)
' returns an array of base 1 which is a list of prime numbers <= num
' this function assumes 1 is not a prime number
Dim a() As Long ' list of primes
Dim numA As Long ' number of primes found
Dim n As Long, i As Long, factor As Long, nguyenTo As Boolean
If num <= 1 Then
  daySNT = Array(0)
  Exit Function
End If
ReDim a(1 To num)
numA = 1
a(numA) = 2 ' here's our first prime number
For n = 3 To num Step 2 ' step thru all odd numbers
  nguyenTo = True
  For i = 2 To numA ' factor the number against current list of primes
    factor = n \ a(i)
    If factor < a(i) Then Exit For ' reaches the limit
    If factor * a(i) = n Then ' not a prime
      nguyenTo = False
      Exit For
    End If
  Next i
  If nguyenTo Then
    numA = numA + 1
    a(numA) = n
  End If
Next n
ReDim Preserve a(1 To numA)
daySNT = a
End Function

Nếu cần hàm xét xem một số có phải là nguyên tố thì như này (hàm này không có tối ưu bằng rổ sàng)

Function LaNguyenTo(n As Long) As Boolean
' hàm xác định một số n có phải là nguyên tố
Select Case n
Case Is <= 1
Case 2
  LaNguyenTo = True
Case Else
  If n And 1 Then ' chi tinh so le
    For i = 3 To Sqr(n) Step 2
      If n Mod i = 0 Then Exit Function
    Next i
    LaNguyenTo = True
  End If
End Select
End Function

 

[batman1]

Nhìn code bài #17, và #18 thấy đơn giản nhưng sao chạy thấy lâu quá. Trên máy cà tàng của tôi nếu N = 10 000 000 (num = 10 000 000) thì chạy khoảng 95 s (85 s).

Tất nhiên code vẫn còn hạn chế về số lượng số nguyên tố. Khi N = 20 000 000 thì số các số nguyên tố vượt quá số dòng trên trang tính (1 270 607 số nguyên tố)