Trả lời cho câu hỏi #245119 trong Python cho Raju
Số nguyên tố đầu tiên
Bạn được cung cấp n đầu vào. Viết một chương trình để in số nguyên tố đầu tiên trong các đầu vào đã cho.
n = int(input("Enter number of integers: ")) numbers = [] for i in range(n): number = int(input("Enter number: ")) isPrime=True if number > 1: for j in range(2, number): if (number % j) == 0: isPrime=False break if isPrime==True: numbers.append(number) print("The first prime number in the given inputs is: "+str(numbers[0]))
Tìm hiểu thêm về sự giúp đỡ của chúng tôi với các bài tập: Python
Số nguyên tố đầu tiên
Bạn được cung cấp n đầu vào. Viết một chương trình để in số nguyên tố đầu tiên trong các đầu vào đã cho.
Đầu vào
Dòng đầu vào đầu tiên là một số nguyên N. Mỗi dòng N tiếp theo có chứa một số nguyên. Giải trình
Trong ví dụ đã cho
5 số nguyên
1
10
4
3
2
Đầu ra phải được
3.
Đầu vào mẫu 1
5
1
10
4
3
2
Đầu ra mẫu 1
3
Đầu vào mẫu 2
4
2
3
5
7
Đầu ra mẫu 2
2
n = int(input("Enter a positive integer: ")) is_primes = [] # list of potential prime numbers(contains primes and non primes) for count in range(n): read = int(input("> ")) is_primes.append(read) non_primes = [] for num in is_primes: if num == 2 or num == 3: pass else: for i in range(2, num): if num % i == 0: non_primes.append(num) break else: pass print(sum(non_primes))
Tìm hiểu thêm về sự giúp đỡ của chúng tôi với các bài tập: Python
Để tham khảo, có một sự khác biệt về tốc độ khá đáng kể giữa các giải pháp đã nêu khác nhau. Đây là một số mã so sánh. Giải pháp được chỉ ra bởi Lennart được gọi là "lịch sử", giải pháp được đề xuất bởi kiến được gọi là "ngây thơ", và một của RC được gọi là "regexp".
from sys import argv from time import time def prime(i, primes): for prime in primes: if not (i == prime or i % prime): return False primes.add(i) return i def historic(n): primes = set([2]) i, p = 2, 0 while True: if prime(i, primes): p += 1 if p == n: return primes i += 1 def naive(n): from itertools import count, islice primes = (n for n in count(2) if all(n % d for d in range(2, n))) return islice(primes, 0, n) def isPrime(n): import re # see //tinyurl.com/3dbhjv return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None def regexp(n): import sys N = int(sys.argv[1]) # number of primes wanted (from command-line) M = 100 # upper-bound of search space l = list() # result list while len(l) < N: l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l M += 100 # increment upper-bound return l[:N] # print result list limited to N elements def dotime(func, n): print func.__name__ start = time() print sorted(list(func(n))) print 'Time in seconds: ' + str(time() - start) if __name__ == "__main__": for func in naive, historic, regexp: dotime(func, int(argv[1]))Đầu ra của điều này trên máy của tôi cho n = 100 là:
naive [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] Time in seconds: 0.0219371318817 historic [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] Time in seconds: 0.00515413284302 regexp [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] Time in seconds: 0.0733318328857Như bạn có thể thấy, có một sự khác biệt khá lớn. Đây là một lần nữa cho 1000 (đã bị xóa đầu ra chính):
naive Time in seconds: 1.49018788338 historic Time in seconds: 0.148319005966 regexp Time in seconds: 29.2350409031