Search Results

Search found 50 results on 2 pages for 'sieve of atkin'.

Page 1/2 | 1 2  | Next Page >

• Why is my implementation of the Sieve of Atkin overlooking numbers close to the specified limit?

  - by Ross G

  My implementation either overlooks primes near the limit or composites near the limit. while some limits work and others don't. I'm am completely confused as to what is wrong. def AtkinSieve (limit): results = [2,3,5] sieve = [False]*limit factor = int(math.sqrt(lim)) for i in range(1,factor): for j in range(1, factor): n = 4*i**2+j**2 if (n <= lim) and (n % 12 == 1 or n % 12 == 5): sieve[n] = not sieve[n] n = 3*i**2+j**2 if (n <= lim) and (n % 12 == 7): sieve[n] = not sieve[n] if i>j: n = 3*i**2-j**2 if (n <= lim) and (n % 12 == 11): sieve[n] = not sieve[n] for index in range(5,factor): if sieve[index]: for jndex in range(index**2, limit, index**2): sieve[jndex] = False for index in range(7,limit): if sieve[index]: results.append(index) return results For example, when I generate a primes to the limit of 1000, the Atkin sieve misses the prime 997, but includes the composite 965. But if I generate up the limit of 5000, the list it returns is completely correct.

  Read the article

• Why is my implementation of the Sieve of Atkin overlooking numbers close to the specified limit?

  - by Ross G

  My implementation either overlooks primes near the limit or composites near the limit. while some limits work and others don't. I'm am completely confused as to what is wrong. def AtkinSieve (limit): results = [2,3,5] sieve = [False]*limit factor = int(math.sqrt(lim)) for i in range(1,factor): for j in range(1, factor): n = 4*i**2+j**2 if (n <= lim) and (n % 12 == 1 or n % 12 == 5): sieve[n] = not sieve[n] n = 3*i**2+j**2 if (n <= lim) and (n % 12 == 7): sieve[n] = not sieve[n] if i>j: n = 3*i**2-j**2 if (n <= lim) and (n % 12 == 11): sieve[n] = not sieve[n] for index in range(5,factor): if sieve[index]: for jndex in range(index**2, limit, index**2): sieve[jndex] = False for index in range(7,limit): if sieve[index]: results.append(index) return results For example, when I generate a primes to the limit of 1000, the Atkin sieve misses the prime 997, but includes the composite 965. But if I generate up the limit of 5000, the list it returns is completely correct.

  Read the article

• Clojure: Avoiding stack overflow in Sieve of Erathosthene?

  - by nixx

  Here's my implementation of Sieve of Erathosthene in Clojure (based on SICP lesson on streams): (defn nats-from [n] (iterate inc n)) (defn divide? [p q] (zero? (rem q p))) (defn sieve [stream] (lazy-seq (cons (first stream) (sieve (remove #(divide? (first stream) %) (rest stream)))))) (def primes (sieve (nats-from 2))) Now, it's all OK when i take first 100 primes: (take 100 primes) But, if i try to take first 1000 primes, program breaks because of stack overflow. I'm wondering if is it possible to change somehow function sieve to become tail-recursive and, still, to preserve "streamnes" of algorithm? Any help???

  Read the article

• Can anyone explain segmented sieve of eratosthenes [on hold]

  - by Utkarsh

  I've searched all over the web on implementation of segmented sieve of eratosthenes. But I found none of them suitable for a beginner. Can anyone explain me the underlying principle behind this method? EDIT: I know that in Sieve of Eratosthenes, we find all primes upto the square root of given number and cross out all multiples of them till the given number. But what do we exactly do in its segmented version?

  Read the article

• Time complexity of Sieve of Eratosthenes algorithm

  - by eSKay

  From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running the sieve on the first 100 numbers (n = 100), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite() would be something like n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n) And to find the next prime number (for example to jump to 7 after crossing out all the numbers that are multiples of 5), the number of operations would be O(n). So, the complexity would be O(n^2). Do you agree?

  Read the article

• The sieve of Eratosthenes in F#

  - by IVlad

  I am interested in an implementation of the sieve of eratosthenes in purely functional F#. I am interested in an implementation of the actual sieve, not the naive functional implementation that isn't really the sieve, so not something like this: let rec PseudoSieve list = match list with | hd::tl -> hd :: (PseudoSieve <| List.filter (fun x -> x % hd <> 0) tl) | [] -> [] The second link above briefly describes an algorithm that would require the use of a multimap, which isn't available in F# as far as I know. The Haskell implementation given uses a map that supports an insertWith method, which I haven't seen available in the F# functional map. Does anyone know a way to translate the given Haskell map code to F#, or perhaps knows of alternative implementation methods or sieving algorithms that are as efficient and better suited for a functional implementation or F#?

  Read the article

• Clojure - tail recursive sieve of Eratosthenes

  - by Konrad Garus

  I have this implementation of the sieve of Eratosthenes in Clojure: (defn sieve [n] (loop [last-tried 2 sift (range 2 (inc n))] (if (or (nil? last-tried) (> last-tried n)) sift (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)] (let [next-to-try (first (filter #(> % last-tried) filtered))] (recur next-to-try filtered)))))) For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?

  Read the article

• Speed up bitstring/bit operations in Python?

  - by Xavier Ho

  I wrote a prime number generator using Sieve of Eratosthenes and Python 3.1. The code runs correctly and gracefully at 0.32 seconds on ideone.com to generate prime numbers up to 1,000,000. # from bitstring import BitString def prime_numbers(limit=1000000): '''Prime number generator. Yields the series 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ... using Sieve of Eratosthenes. ''' yield 2 sub_limit = int(limit**0.5) flags = [False, False] + [True] * (limit - 2) # flags = BitString(limit) # Step through all the odd numbers for i in range(3, limit, 2): if flags[i] is False: # if flags[i] is True: continue yield i # Exclude further multiples of the current prime number if i <= sub_limit: for j in range(i*3, limit, i<<1): flags[j] = False # flags[j] = True The problem is, I run out of memory when I try to generate numbers up to 1,000,000,000. flags = [False, False] + [True] * (limit - 2) MemoryError As you can imagine, allocating 1 billion boolean values (1 byte 4 or 8 bytes (see comment) each in Python) is really not feasible, so I looked into bitstring. I figured, using 1 bit for each flag would be much more memory-efficient. However, the program's performance dropped drastically - 24 seconds runtime, for prime number up to 1,000,000. This is probably due to the internal implementation of bitstring. You can comment/uncomment the three lines to see what I changed to use BitString, as the code snippet above. My question is, is there a way to speed up my program, with or without bitstring?

  Read the article

• Why Stream/lazy val implementation using is faster than ListBuffer one

  - by anrizal

  I coded the following implementation of lazy sieve algorithms using Stream and lazy val below : def primes(): Stream[Int] = { lazy val ps = 2 #:: sieve(3) def sieve(p: Int): Stream[Int] = { p #:: sieve( Stream.from(p + 2, 2). find(i=> ps.takeWhile(j => j * j <= i). forall(i % _ > 0)).get) } ps } and the following implementation using (mutable) ListBuffer: import scala.collection.mutable.ListBuffer def primes(): Stream[Int] = { def sieve(p: Int, ps: ListBuffer[Int]): Stream[Int] = { p #:: { val nextprime = Stream.from(p + 2, 2). find(i=> ps.takeWhile(j => j * j <= i). forall(i % _ > 0)).get sieve(nextprime, ps += nextprime) } } sieve(3, ListBuffer(3))} When I did primes().takeWhile(_ < 1000000).size , the first implementation is 3 times faster than the second one. What's the explanation for this ? I edited the second version: it should have been sieve(3, ListBuffer(3)) instead of sieve(3, ListBuffer()) .

  Read the article

• "EXC_BAD_ACCESS: Unable to restore previously selected frame" Error, Array size?

  - by Job

  Hi there, I have an algorithm for creating the sieve of Eratosthenes and pulling primes from it. It lets you enter a max value for the sieve and the algorithm gives you the primes below that value and stores these in a c-style array. Problem: Everything works fine with values up to 500.000, however when I enter a large value -while running- it gives me the following error message in xcode: Program received signal: “EXC_BAD_ACCESS”. warning: Unable to restore previously selected frame. Data Formatters temporarily unavailable, will re-try after a 'continue'. (Not safe to call dlopen at this time.) My first idea was that I didn't use large enough variables, but as I am using 'unsigned long long int', this should not be the problem. Also the debugger points me to a point in my code where a point in the array get assigned a value. Therefore I wonder is there a maximum limit to an array? If yes: should I use NSArray instead? If no, then what is causing this error based on this information? EDIT: This is what the code looks like (it's not complete, for it fails at the last line posted). I'm using garbage collection. /*--------------------------SET UP--------------------------*/ unsigned long long int upperLimit = 550000; // unsigned long long int sieve[upperLimit]; unsigned long long int primes[upperLimit]; unsigned long long int indexCEX; unsigned long long int primesCounter = 0; // Fill sieve with 2 to upperLimit for(unsigned long long int indexA = 0; indexA < upperLimit-1; ++indexA) { sieve[indexA] = indexA+2; } unsigned long long int prime = 2; /*-------------------------CHECK & FIND----------------------------*/ while(!((prime*prime) > upperLimit)) { //check off all multiples of prime for(unsigned long long int indexB = prime-2; indexB < upperLimit-1; ++indexB) { // Multiple of prime = 0 if(sieve[indexB] != 0) { if(sieve[indexB] % prime == 0) { sieve[indexB] = 0; } } } /*---------------- Search for next prime ---------------*/ // index of current prime + 1 unsigned long long int indexC = prime - 1; while(sieve[indexC] == 0) { ++indexC; } prime = sieve[indexC]; // Store prime in primes[] primes[primesCounter] = prime; // This is where the code fails if upperLimit > 500000 ++primesCounter; indexCEX = indexC + 1; } As you may or may not see, is that I am -very much- a beginner. Any other suggestions are welcome of course :)

  Read the article

• Can't connect to smtp (postfix, dovecot) after making a change and trying to change it back

  - by UberBrainChild

  I am using postfix and dovecot along with zpanel and I tried enabling SSL and then turned it off as I did not have SSL configured yet and I realized it was a bit stupid at the time. I am using CentOS 6.4. I get the following error in the mail log. (I changed my host name to "myhostname" and my domain to "mydomain.com") Oct 20 01:49:06 myhostname postfix/smtpd[4714]: connect from mydomain.com[127.0.0.1] Oct 20 01:49:16 myhostname postfix/smtpd[4714]: fatal: no SASL authentication mechanisms Oct 20 01:49:17 myhostname postfix/master[4708]: warning: process /usr/libexec/postfix/smtpd pid 4714 exit status 1 Oct 20 01:49:17 amyhostname postfix/master[4708]: warning: /usr/libexec/postfix/smtpd: bad command startup -- throttling Reading on forums and similar questions I figured it was just a service that was not running or installed. However I can see that saslauthd is currently up and running on my system and restarting it does not help. Here is my postfix master.cf # # Postfix master process configuration file. For details on the format # of the file, see the Postfix master(5) manual page. # # ***** Unused items removed ***** # ========================================================================== # service type private unpriv chroot wakeup maxproc command + args # (yes) (yes) (yes) (never) (100) # ========================================================================== smtp inet n - n - - smtpd # -o content_filter=smtp-amavis:127.0.0.1:10024 # -o receive_override_options=no_address_mappings pickup fifo n - n 60 1 pickup submission inet n - - - - smtpd -o content_filter= -o receive_override_options=no_header_body_checks cleanup unix n - n - 0 cleanup qmgr fifo n - n 300 1 qmgr #qmgr fifo n - n 300 1 oqmgr tlsmgr unix - - n 1000? 1 tlsmgr rewrite unix - - n - - trivial-rewrite bounce unix - - n - 0 bounce defer unix - - n - 0 bounce trace unix - - n - 0 bounce verify unix - - n - 1 verify flush unix n - n 1000? 0 flush proxymap unix - - n - - proxymap smtp unix - - n - - smtp smtps inet n - - - - smtpd # When relaying mail as backup MX, disable fallback_relay to avoid MX loops relay unix - - n - - smtp -o fallback_relay= # -o smtp_helo_timeout=5 -o smtp_connect_timeout=5 showq unix n - n - - showq error unix - - n - - error discard unix - - n - - discard local unix - n n - - local virtual unix - n n - - virtual lmtp unix - - n - - lmtp anvil unix - - n - 1 anvil scache unix - - n - 1 scache # # ==================================================================== # Interfaces to non-Postfix software. Be sure to examine the manual # pages of the non-Postfix software to find out what options it wants. # ==================================================================== maildrop unix - n n - - pipe flags=DRhu user=vmail argv=/usr/local/bin/maildrop -d ${recipient} uucp unix - n n - - pipe flags=Fqhu user=uucp argv=uux -r -n -z -a$sender - $nexthop!rmail ($recipient) ifmail unix - n n - - pipe flags=F user=ftn argv=/usr/lib/ifmail/ifmail -r $nexthop ($recipient) bsmtp unix - n n - - pipe flags=Fq. user=foo argv=/usr/local/sbin/bsmtp -f $sender $nexthop $recipient # # spam/virus section # smtp-amavis unix - - y - 2 smtp -o smtp_data_done_timeout=1200 -o disable_dns_lookups=yes -o smtp_send_xforward_command=yes 127.0.0.1:10025 inet n - y - - smtpd -o content_filter= -o smtpd_helo_restrictions= -o smtpd_sender_restrictions= -o smtpd_recipient_restrictions=permit_mynetworks,reject -o mynetworks=127.0.0.0/8 -o smtpd_error_sleep_time=0 -o smtpd_soft_error_limit=1001 -o smtpd_hard_error_limit=1000 -o receive_override_options=no_header_body_checks -o smtpd_bind_address=127.0.0.1 -o smtpd_helo_required=no -o smtpd_client_restrictions= -o smtpd_restriction_classes= -o disable_vrfy_command=no -o strict_rfc821_envelopes=yes # # Dovecot LDA dovecot unix - n n - - pipe flags=DRhu user=vmail:mail argv=/usr/libexec/dovecot/deliver -d ${recipient} # # Vacation mail vacation unix - n n - - pipe flags=Rq user=vacation argv=/var/spool/vacation/vacation.pl -f ${sender} -- ${recipient} And here is dovecot ## ## Dovecot config file ## listen = * disable_plaintext_auth = no protocols = imap pop3 lmtp sieve auth_mechanisms = plain login passdb { driver = sql args = /etc/zpanel/configs/dovecot2/dovecot-mysql.conf } userdb { driver = sql } userdb { driver = sql args = /etc/zpanel/configs/dovecot2/dovecot-mysql.conf } mail_location = maildir:/var/zpanel/vmail/%d/%n first_valid_uid = 101 #last_valid_uid = 0 first_valid_gid = 12 #last_valid_gid = 0 #mail_plugins = mailbox_idle_check_interval = 30 secs maildir_copy_with_hardlinks = yes service imap-login { inet_listener imap { port = 143 } } service pop3-login { inet_listener pop3 { port = 110 } } service lmtp { unix_listener lmtp { #mode = 0666 } } service imap { vsz_limit = 256M } service pop3 { } service auth { unix_listener auth-userdb { mode = 0666 user = vmail group = mail } # Postfix smtp-auth unix_listener /var/spool/postfix/private/auth { mode = 0666 user = postfix group = postfix } } service auth-worker { } service dict { unix_listener dict { mode = 0666 user = vmail group = mail } } service managesieve-login { inet_listener sieve { port = 4190 } service_count = 1 process_min_avail = 0 vsz_limit = 64M } service managesieve { } lda_mailbox_autocreate = yes lda_mailbox_autosubscribe = yes protocol lda { mail_plugins = quota sieve postmaster_address = [email protected] } protocol imap { mail_plugins = quota imap_quota trash imap_client_workarounds = delay-newmail } lmtp_save_to_detail_mailbox = yes protocol lmtp { mail_plugins = quota sieve } protocol pop3 { mail_plugins = quota pop3_client_workarounds = outlook-no-nuls oe-ns-eoh } protocol sieve { managesieve_max_line_length = 65536 managesieve_implementation_string = Dovecot Pigeonhole managesieve_max_compile_errors = 5 } dict { quotadict = mysql:/etc/zpanel/configs/dovecot2/dovecot-dict-quota.conf } plugin { # quota = dict:User quota::proxy::quotadict quota = maildir:User quota acl = vfile:/etc/dovecot/acls trash = /etc/zpanel/configs/dovecot2/dovecot-trash.conf sieve_global_path = /var/zpanel/sieve/globalfilter.sieve sieve = ~/dovecot.sieve sieve_dir = ~/sieve sieve_global_dir = /var/zpanel/sieve/ #sieve_extensions = +notify +imapflags sieve_max_script_size = 1M #sieve_max_actions = 32 #sieve_max_redirects = 4 } log_path = /var/log/dovecot.log info_log_path = /var/log/dovecot-info.log debug_log_path = /var/log/dovecot-debug.log mail_debug=yes ssl = no Does anyone have any ideas or tips on what I can try to get this working? Thanks for all the help EDIT: Output of postconf -n alias_database = hash:/etc/aliases alias_maps = hash:/etc/aliases broken_sasl_auth_clients = yes command_directory = /usr/sbin config_directory = /etc/postfix daemon_directory = /usr/libexec/postfix debug_peer_level = 2 delay_warning_time = 4 disable_vrfy_command = yes html_directory = no inet_interfaces = all mail_owner = postfix mailq_path = /usr/bin/mailq.postfix manpage_directory = /usr/share/man mydestination = localhost.$mydomain, localhost mydomain = control.yourdomain.com myhostname = control.yourdomain.com mynetworks = all newaliases_path = /usr/bin/newaliases.postfix queue_directory = /var/spool/postfix readme_directory = /usr/share/doc/postfix-2.2.2/README_FILES recipient_delimiter = + relay_domains = proxy:mysql:/etc/zpanel/configs/postfix/mysql-relay_domains_maps.cf sample_directory = /usr/share/doc/postfix-2.2.2/samples sendmail_path = /usr/sbin/sendmail.postfix setgid_group = postdrop smtp_use_tls = no smtpd_client_restrictions = smtpd_data_restrictions = reject_unauth_pipelining smtpd_helo_required = yes smtpd_helo_restrictions = smtpd_recipient_restrictions = permit_sasl_authenticated, permit_mynetworks, reject_unauth_destination, reject_non_fqdn_sender, reject_non_fqdn_recipient, reject_unknown_recipient_domain smtpd_sasl_auth_enable = yes smtpd_sasl_local_domain = $myhostname smtpd_sasl_path = private/auth smtpd_sasl_security_options = noanonymous smtpd_sasl_type = dovecot smtpd_sender_restrictions = smtpd_use_tls = no soft_bounce = yes transport_maps = hash:/etc/postfix/transport unknown_local_recipient_reject_code = 550 virtual_alias_maps = proxy:mysql:/etc/zpanel/configs/postfix/mysql-virtual_alias_maps.cf, regexp:/etc/zpanel/configs/postfix/virtual_regexp virtual_gid_maps = static:12 virtual_mailbox_base = /var/zpanel/vmail virtual_mailbox_domains = proxy:mysql:/etc/zpanel/configs/postfix/mysql-virtual_domains_maps.cf virtual_mailbox_maps = proxy:mysql:/etc/zpanel/configs/postfix/mysql-virtual_mailbox_maps.cf virtual_minimum_uid = 101 virtual_transport = dovecot virtual_uid_maps = static:101

  Read the article

• Recursive function causing a stack overflow

  - by dbyrne

  I am trying to write a simple sieve function to calculate prime numbers in clojure. I've seen this question about writing an efficient sieve function, but I am not to that point yet. Right now I am just trying to write a very simple (and slow) sieve. Here is what I have come up with: (defn sieve [potentials primes] (if-let [p (first potentials)] (recur (filter #(not= (mod % p) 0) potentials) (conj primes p)) primes)) For small ranges it works fine, but causes a stack overflow for large ranges: user=> (sieve (range 2 30) []) [2 3 5 7 11 13 17 19 23 29] user=> (sieve (range 2 15000) []) java.lang.StackOverflowError (NO_SOURCE_FILE:0) I thought that by using recur this would be a non-stack-consuming looping construct? What am I missing?

  Read the article

• ruby comma operator and step question

  - by ryan_m

  so, i'm trying to learn ruby by doing some project euler questions, and i've run into a couple things i can't explain, and the comma ?operator? is in the middle of both. i haven't been able to find good documentation for this, maybe i'm just not using the google as I should, but good ruby documentation seems a little sparse . . . 1: how do you describe how this is working? the first snippet is the ruby code i don't understand, the second is the code i wrote that does the same thing only after painstakingly tracing the first: #what is this doing? cur, nxt = nxt, cur + nxt #this, apparently, but how to describe the above? nxt = cur + nxt cur = nxt - cur 2: in the following example, how do you describe what the line with 'step' is doing? from what i can gather, the step command works like (range).step(step_size), but this seems to be doing (starting_point).step(ending_point, step_size). Am i right with this assumption? where do i find good doc of this? #/usr/share/doc/ruby1.9.1-examples/examples/sieve.rb # sieve of Eratosthenes max = Integer(ARGV.shift || 100) sieve = [] for i in 2 .. max sieve[i] = i end for i in 2 .. Math.sqrt(max) next unless sieve[i] (i*i).step(max, i) do |j| sieve[j] = nil end end puts sieve.compact.join(", ")

  Read the article

• Java 8 Stream, getting head and tail

  - by lyomi

  Java 8 introduced a Stream class that resembles Scala's Stream, a powerful lazy construct using which it is possible to do something like this very concisely: def from(n: Int): Stream[Int] = n #:: from(n+1) def sieve(s: Stream[Int]): Stream[Int] = { s.head #:: sieve(s.tail filter (_ % s.head != 0)) } val primes = sieve(from(2)) primes takeWhile(_ < 1000) print // prints all primes less than 1000 I wondered if it is possible to do this in Java 8, so I wrote something like this: IntStream from(int n) { return IntStream.iterate(n, m -> m + 1); } IntStream sieve(IntStream s) { int head = s.findFirst().getAsInt(); return IntStream.concat(IntStream.of(head), sieve(s.skip(1).filter(n -> n % head != 0))); } IntStream primes = sieve(from(2)); PrimitiveIterator.OfInt it = primes.iterator(); for (int prime = it.nextInt(); prime < 1000; prime = it.nextInt()) { System.out.println(prime); } Fairly simple, but it produces java.lang.IllegalStateException: stream has already been operated upon or closed because both findFirst() and skip() is a terminal operation on Stream which can be done only once. I don't really have to use up the stream twice since all I need is the first number in the stream and the rest as another stream, i.e. equivalent of Scala's Stream.head and Stream.tail. Is there a method in Java 8 Stream that I can achieve this? Thanks.

  Read the article

• Python: speed up removal of every n-th element from list.

  - by ChristopheD

  I'm trying to solve this programming riddle and althought the solution (see code below) works correct, it is too slow for succesful submission. Any pointers as how to make this run faster? (removal of every n-th element from a list)? Or suggestions for a better algorithm to calculate the same; seems I can't think of anything else then brute-force for now... Basically the task at hand is: GIVEN: L = [2,3,4,5,6,7,8,9,10,11,........] 1. Take the first remaining item in list L (in the general case 'n'). Move it to the 'lucky number list'. Then drop every 'n-th' item from the list. 2. Repeat 1 TASK: Calculate the n-th number from the 'lucky number list' ( 1 <= n <= 3000) My current code (it calculates the 3000 first lucky numbers in about a second on my machine - but unfortunately too slow): """ SPOJ Problem Set (classical) 1798. Assistance Required URL: http://www.spoj.pl/problems/ASSIST/ """ sieve = range(3, 33900, 2) luckynumbers = [2] while True: wanted_n = input() if wanted_n == 0: break while len(luckynumbers) < wanted_n: item = sieve[0] luckynumbers.append(item) items_to_delete = set(sieve[::item]) sieve = filter(lambda x: x not in items_to_delete, sieve) print luckynumbers[wanted_n-1]

  Read the article

• Segmentation Fault?

  - by user336808

  Hello, when I run this program while inputting a number greater than 46348, I get a segmentation fault. For any values below it, the program works perfectly. I am using CodeBlocks 8.02 on Ubuntu 10.04 64-bit. The code is as follows: int main() { int number = 46348; vector<bool> sieve(number+1,false); vector<int> primes; sieve[0] = true; sieve[1] = true; for(int i = 2; i <= number; i++) { if(sieve[i]==false) { primes.push_back(i); int temp = i*i; while(temp <= number) { sieve[temp] = true; temp = temp + i; } } } for(int i = 0; i < primes.size(); i++) cout << primes[i] << " "; return 0; }

  Read the article

• Correct answer will not output

  - by rEgonicS

  I made a program that returns the sum of all primes under 2 million. I really have no idea what's going on with this one, I get 142891895587 as my answer when the correct answer is 142913828922. It seems like its missing a few primes in there. I'm pretty sure the getPrime function works as it is supposed to. I used it a couple times before and worked correctly than. The code is as follows: vector<int> getPrimes(int number); int main() { unsigned long int sum = 0; vector<int> primes = getPrimes(2000000); for(int i = 0; i < primes.size(); i++) { sum += primes[i]; } cout << sum; return 0; } vector<int> getPrimes(int number) { vector<bool> sieve(number+1,false); vector<int> primes; sieve[0] = true; sieve[1] = true; for(int i = 2; i <= number; i++) { if(sieve[i]==false) { primes.push_back(i); unsigned long int temp = i*i; while(temp <= number) { sieve[temp] = true; temp = temp + i; } } } return primes; }

  Read the article

• Dovecot starting and running, but not listening on any port

  - by Dženis Macanovic

  Among others things I'm in charge of a Debian GNU/Linux (Wheezy) DomU for the mail services of the company i work for. Yesterday one HDD that was used for this particular server has died. After installing Debian again, Dovecot decided to no longer listen on any ports (checked with netstat -l). Other services (like Postfix and MySQL) work without problems. dovecot -n: # 2.1.7: /etc/dovecot/dovecot.conf # OS: Linux 3.2.0-3-amd64 x86_64 Debian wheezy/sid ext3 auth_mechanisms = plain login disable_plaintext_auth = no first_valid_uid = 150 last_valid_uid = 150 mail_gid = mail mail_location = maildir:/var/vmail/%d/%n mail_uid = vmail namespace inbox { inbox = yes location = prefix = } pass db { args = /etc/dovecot/dovecot-sql.conf.ext driver = sql } plugin { sieve = ~/.dovecot.sieve sieve_dir = ~/sieve } service auth { unix_listener /var/spool/postfix/private/auth { group = postfix mode = 0660 user = postfix } unix_listener auth-userdb { group = mail mode = 0666 user = vmail } } service imap-login { inet_listener imaps { port = 993 ssl = yes } } service pop3-login { inet_listener pop3s { port = 995 ssl = yes } } ssl_cert = </etc/ssl/private/mail.crt ssl_key = </etc/ssl/private/mail.key userdb { args = /etc/dovecot/dovecot-sql.conf.ext driver = sql } protocol imap { mail_max_userip_connections = 25 } UID 150 is vmail (I double checked file permissions). I didn't install Dovecot from source, but via apt from the official Debian US mirror. There are no messages concerning Dovecot in /var/log/syslog except for: Oct 21 06:36:29 server dovecot: master: Dovecot v2.1.7 starting up (core dumps disabled) Any ideas?

  Read the article

• Fastest way to list all primes below N in python

  - by jbochi

  This is the best algorithm I could come up with after struggling with a couple of Project Euler's questions. def get_primes(n): numbers = set(range(n, 1, -1)) primes = [] while numbers: p = numbers.pop() primes.append(p) numbers.difference_update(set(range(p*2, n+1, p))) return primes >>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1) 1.1499958793645562 Can it be made even faster? EDIT: This code has a flaw: Since numbers is an unordered set, there is no guarantee that numbers.pop() will remove the lowest number from the set. Nevertheless, it works (at least for me) for some input numbers: >>> sum(get_primes(2000000)) 142913828922L #That's the correct sum of all numbers below 2 million >>> 529 in get_primes(1000) False >>> 529 in get_primes(530) True EDIT: The rank so far (pure python, no external sources, all primes below 1 million): Sundaram's Sieve implementation by myself: 327ms Daniel's Sieve: 435ms Alex's recipe from Cookbok: 710ms EDIT: ~unutbu is leading the race.

  Read the article

• Express any number as the sum of 4 prime numbers [Doubts]

  - by WarDoGG

  I was give a problem to express any number as sum of 4 prime numbers. Conditions: Not allowed to use any kind of database. Maximum execution time : 3 seconds Numbers only till 100,000 If the splitting is NOT possible, then return -1 What i did : using the sieve of eratosthenes, i calculated all prime numbers till the specified number. looked up a concept called goldbach conjecture which expresses an even number as the summation of 2 primes. However, i am stuck beyond that. Can anyone help me on this one as to what approach u might take ? The sieve of eratosthenes is taking 2 seconds to count primes till 100,000 :(((

  Read the article

• Relay Access Denied (State 13) Postfix + Dovecot + Mysql

  - by Pierre Jeptha

  So we have been scratching our heads for quite some time over this relay issue that has presented itself since we re-built our mail-server after a failed Webmin update. We are running Debian Karmic with postfix 2.6.5 and Dovecot 1.1.11, sourcing from a Mysql database and authenticating with SASL2 and PAM. Here are the symptoms of our problem: 1) When users are on our local network they can send and receive 100% perfectly fine. 2) When users are off our local network and try to send to domains not of this mail server (ie. gmail) they get the "Relay Access Denied" error. However users can send to domains of this mail server when off the local network fine. 3) We host several virtual domains on this mailserver, the primary domain being airnet.ca. The rest of our virtual domains (ex. jeptha.ca) cannot receive email from domains not hosted by this mailserver (ie. gmail and such cannot send to them). They receive bounce backs of "Relay Access Denied (State 13)". This is regardless of whether they are on our local network or not, which is why it is so urgent for us to get this solved. Here is our main.cf from postfix: myhostname = mail.airnet.ca mydomain = airnet.ca smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu) biff = no smtpd_sasl_type = dovecot queue_directory = /var/spool/postfix smtpd_sasl_path = private/auth smtpd_sender_restrictions = permit_mynetworks permit_sasl_authenticated smtp_sasl_auth_enable = yes smtpd_sasl_auth_enable = yes append_dot_mydomain = no readme_directory = no smtp_tls_security_level = may smtpd_tls_security_level = may smtp_tls_note_starttls_offer = yes smtpd_tls_key_file = /etc/ssl/private/ssl-cert-snakeoil.key smtpd_tls_cert_file = /etc/ssl/certs/ssl-cert-snakeoil.pem smtpd_tls_loglevel = 1 smtpd_tls_received_header = yes smtpd_tls_auth_only = no alias_maps = proxy:mysql:/etc/postfix/mysql/alias.cf hash:/etc/aliases alias_database = hash:/etc/aliases mydestination = mail.airnet.ca, airnet.ca, localhost.$mydomain mailbox_command = procmail -a "$EXTENSION" mailbox_size_limit = 0 recipient_delimiter = + local_recipient_maps = $alias_maps $virtual_mailbox_maps proxy:unix:passwd.byname home_mailbox = /var/virtual/ mail_spool_directory = /var/spool/mail mailbox_transport = maildrop smtpd_helo_required = yes disable_vrfy_command = yes smtpd_etrn_restrictions = reject smtpd_data_restrictions = reject_unauth_pipelining, permit show_user_unknown_table_name = no proxy_read_maps = $local_recipient_maps $mydestination $virtual_alias_maps $virtual_alias_domains $virtual_mailbox_maps $virtual_mailbox_domains $relay_recipient_maps $relay_domains $canonical_maps $sender_canonical_maps $recipient_canonical_maps $relocated_maps $transport_maps $mynetworks $virtual_mailbox_limit_maps $virtual_uid_maps $virtual_gid_maps virtual_alias_domains = message_size_limit = 20971520 transport_maps = proxy:mysql:/etc/postfix/mysql/vdomain.cf virtual_mailbox_maps = proxy:mysql:/etc/postfix/mysql/vmailbox.cf virtual_alias_maps = proxy:mysql:/etc/postfix/mysql/alias.cf hash:/etc/mailman/aliases virtual_uid_maps = proxy:mysql:/etc/postfix/mysql/vuid.cf virtual_gid_maps = proxy:mysql:/etc/postfix/mysql/vgid.cf virtual_mailbox_base = / virtual_mailbox_limit = 209715200 virtual_mailbox_extended = yes virtual_create_maildirsize = yes virtual_mailbox_limit_maps = proxy:mysql:/etc/postfix/mysql/vmlimit.cf virtual_mailbox_limit_override = yes virtual_mailbox_limit_inbox = no virtual_overquote_bounce = yes virtual_minimum_uid = 1 maximal_queue_lifetime = 1d bounce_queue_lifetime = 4h delay_warning_time = 1h append_dot_mydomain = no qmgr_message_active_limit = 500 broken_sasl_auth_clients = yes smtpd_sasl_path = private/auth smtpd_sasl_local_domain = $myhostname smtpd_sasl_security_options = noanonymous smtpd_sasl_authenticated_header = yes smtp_bind_address = 142.46.193.6 relay_domains = $mydestination mynetworks = 127.0.0.0, 142.46.193.0/25 inet_interfaces = all inet_protocols = all And here is the master.cf from postfix: # ========================================================================== # service type private unpriv chroot wakeup maxproc command + args # (yes) (yes) (yes) (never) (100) # ========================================================================== smtp inet n - - - - smtpd #submission inet n - - - - smtpd # -o smtpd_tls_security_level=encrypt # -o smtpd_sasl_auth_enable=yes # -o smtpd_client_restrictions=permit_sasl_authenticated,reject # -o milter_macro_daemon_name=ORIGINATING #smtps inet n - - - - smtpd # -o smtpd_tls_wrappermode=yes # -o smtpd_sasl_auth_enable=yes # -o smtpd_client_restrictions=permit_sasl_authenticated,reject # -o milter_macro_daemon_name=ORIGINATING #628 inet n - - - - qmqpd pickup fifo n - - 60 1 pickup cleanup unix n - - - 0 cleanup qmgr fifo n - n 300 1 qmgr #qmgr fifo n - - 300 1 oqmgr tlsmgr unix - - - 1000? 1 tlsmgr rewrite unix - - - - - trivial-rewrite bounce unix - - - - 0 bounce defer unix - - - - 0 bounce trace unix - - - - 0 bounce verify unix - - - - 1 verify flush unix n - - 1000? 0 flush proxymap unix - - n - - proxymap proxywrite unix - - n - 1 proxymap smtp unix - - - - - smtp # When relaying mail as backup MX, disable fallback_relay to avoid MX loops relay unix - - - - - smtp -o smtp_fallback_relay= # -o smtp_helo_timeout=5 -o smtp_connect_timeout=5 showq unix n - - - - showq error unix - - - - - error retry unix - - - - - error discard unix - - - - - discard local unix - n n - - local virtual unix - n n - - virtual lmtp unix - - - - - lmtp anvil unix - - - - 1 anvil scache unix - - - - 1 scache maildrop unix - n n - - pipe flags=DRhu user=vmail argv=/usr/bin/maildrop -d ${recipient} # # See the Postfix UUCP_README file for configuration details. # uucp unix - n n - - pipe flags=Fqhu user=uucp argv=uux -r -n -z -a$sender - $nexthop!rmail ($recipient) # # Other external delivery methods. # ifmail unix - n n - - pipe flags=F user=ftn argv=/usr/lib/ifmail/ifmail -r $nexthop ($recipient) bsmtp unix - n n - - pipe flags=Fq. user=bsmtp argv=/usr/lib/bsmtp/bsmtp -t$nexthop -f$sender $recipient scalemail-backend unix - n n - 2 pipe flags=R user=scalemail argv=/usr/lib/scalemail/bin/scalemail-store ${nexthop} ${user} ${extension} mailman unix - n n - - pipe flags=FR user=list argv=/usr/lib/mailman/bin/postfix-to-mailman.py ${nexthop} ${user} spfpolicy unix - n n - - spawn user=nobody argv=/usr/bin/perl /usr/sbin/postfix-policyd-spf-perl smtp-amavis unix - - n - 4 smtp -o smtp_data_done_timeout=1200 -o smtp_send_xforward_command=yes -o disable_dns_lookups=yes #127.0.0.1:10025 inet n - n - - smtpd dovecot unix - n n - - pipe flags=DRhu user=dovecot:21pever1lcha0s argv=/usr/lib/dovecot/deliver -d ${recipient Here is Dovecot.conf protocols = imap imaps pop3 pop3s disable_plaintext_auth = no log_path = /etc/dovecot/logs/err info_log_path = /etc/dovecot/logs/info log_timestamp = "%Y-%m-%d %H:%M:%S ". syslog_facility = mail ssl_listen = 142.46.193.6 ssl_disable = no ssl_cert_file = /etc/ssl/certs/ssl-cert-snakeoil.pem ssl_key_file = /etc/ssl/private/ssl-cert-snakeoil.key mail_location = mbox:~/mail:INBOX=/var/virtual/%d/mail/%u mail_privileged_group = mail mail_debug = yes protocol imap { login_executable = /usr/lib/dovecot/imap-login mail_executable = /usr/lib/dovecot/rawlog /usr/lib/dovecot/imap mail_executable = /usr/lib/dovecot/gdbhelper /usr/lib/dovecot/imap mail_executable = /usr/lib/dovecot/imap imap_max_line_length = 65536 mail_max_userip_connections = 20 mail_plugin_dir = /usr/lib/dovecot/modules/imap login_greeting_capability = yes } protocol pop3 { login_executable = /usr/lib/dovecot/pop3-login mail_executable = /usr/lib/dovecot/pop3 pop3_enable_last = no pop3_uidl_format = %08Xu%08Xv mail_max_userip_connections = 10 mail_plugin_dir = /usr/lib/dovecot/modules/pop3 } protocol managesieve { sieve=~/.dovecot.sieve sieve_storage=~/sieve } mail_plugin_dir = /usr/lib/dovecot/modules/lda auth_executable = /usr/lib/dovecot/dovecot-auth auth_process_size = 256 auth_cache_ttl = 3600 auth_cache_negative_ttl = 3600 auth_username_chars = abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890.-_@ auth_verbose = yes auth_debug = yes auth_debug_passwords = yes auth_worker_max_count = 60 auth_failure_delay = 2 auth default { mechanisms = plain login passdb sql { args = /etc/dovecot/dovecot-sql.conf } userdb sql { args = /etc/dovecot/dovecot-sql.conf } socket listen { client { path = /var/spool/postfix/private/auth mode = 0660 user = postfix group = postfix } master { path = /var/run/dovecot/auth-master mode = 0600 } } } Please, if you require anything do not hesistate, I will post it ASAP. Any help or suggestions are greatly appreciated! Thanks, Pierre

  Read the article

• Algorithm to calculate the number of divisors of a given number

  - by sker

  What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number? It'll be great if you could provide pseudocode or a link to some example. EDIT: All the answers have been very helpful, thank you. I'm implementing the Sieve of Atkin and then I'm going to use something similar to what Jonathan Leffler indicated. The link posted by Justin Bozonier has further information on what I wanted.

  Read the article

• Go and a bad prime number algorithm

  - by anonymous

  I wrote this prime number sieving algorithm and it doesn't run properly. I can't find the error in the algorithm itself. Could someone help me? This is what it's supposed to print: [2 3 5 7 11 13 17 19 23 29] Versus what it actually prints: [3 5 7 11 13 17 19 23 25 29] . package main import "fmt" func main() { var primes = sieve(makeNumbers(29)) fmt.Printf("%d\n", primes); } func makeNumbers(n int) []int { var numbers = make([]int, n - 1) for i := 0; i < len(numbers); i++ { numbers[i] = i + 2 } return numbers } func sieve(numbers []int) []int { var numCopy = numbers var max = numbers[len(numbers)-1] var sievedNumbers = make([]int, 0) for i := 0; numCopy[i]*numCopy[i] <= max; i++ { for j := i; j < len(numCopy); j++ { if numCopy[j] % numCopy[i] != 0 || j == i { sievedNumbers = append(sievedNumbers, numCopy[j]) } } numCopy = sievedNumbers sievedNumbers = make([]int, 0) } return numCopy }

  Read the article

• Is this mingw bug ?

  - by Debanjan

  Hi, I have been trying to execute this program on my migw ,through code::blocks, #include <string.h> #include <math.h> #include <stdio.h> #define N 100 int p[N / 64]; int pr[N]; int cnt; void sieve() { int i,j; for(i=0;i<N;i++) pr[i]=1; pr[0]=pr[1]=0; for(i=2;i<N;i++) if(pr[i]) { p[cnt]=i; cnt++; for(j=i+i;j<=N;j+=i) pr[j]=0; } } int main(){ sieve(); int i; for(i=0;i<cnt;i++) printf("%d ",p[i]); puts(""); printf("Total number of prime numbers : %d",cnt); return 0; } In My system the output is : 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Total number of prime numbers : 22 Which is completely insane,since I am completely sure about the implementation of my algorithm. So I decided to try it in Ideone where it gives correct output.Can anybody point out the reason ?

  Read the article

• Finding a prime number after a given number

  - by avd

  How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11. I would like to know some ideas on best algorithms to do this. One method that I thought of was generate primes numbers through the Sieve of Eratosthenes, and then find the prime after the given number.

  Read the article

1 2  | Next Page >