{"entities":{"Q1336051":{"pageid":1346790,"ns":120,"title":"Item:Q1336051","lastrevid":70170651,"modified":"2026-04-13T12:55:28Z","type":"item","id":"Q1336051","labels":{"en":{"language":"en","value":"Two fast parallel prime number sieves"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 653290"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$FD805C6B-359B-4B0F-8019-4F0C03DB2124","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02c965b60b742b644772cf32e19d534e57a51bf7","datavalue":{"value":{"text":"Two fast parallel prime number sieves","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1336051$961F9C41-5D57-49CF-86E2-1796C6E74871","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b7c4c9601b89789bb649996a801b393691138bc","datavalue":{"value":"0807.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$D93A6AAA-AA64-41EB-ADF4-65B5901B9BC0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7712420576ab073f1af3f431c71f5fc7fbb67a0d","datavalue":{"value":{"entity-type":"item","numeric-id":582118,"id":"Q582118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$7AA497DC-43A3-46E5-BFA9-673E08895AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0abd1dceb9269c72f5389f044a132399ba8466ee","datavalue":{"value":{"entity-type":"item","numeric-id":991751,"id":"Q991751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$5A3398CF-6D41-4CA4-BF94-FC49C570C874","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$E7BF8D32-0637-4A18-BB1D-DD233C3C80A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35d39e210be1143825b67c9418f16b393bda66a7","datavalue":{"value":{"time":"+1994-10-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1336051$3675F774-F3F5-4C65-80CE-78933755A138","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc9804fd5699db16fd479c7d02c0b19fdcd1ba71","datavalue":{"value":"The paper presents two parallel algorithms that list all prime numbers up to \\(n\\), a problem for which sequential algorithms of complexity \\(O(n/ \\log \\log n)\\) are known [\\textit{H. G. Mairson}, Commun. ACM 20, 664-669 (1977; Zbl 0355.68040); \\textit{P. Pritchard}, Comm. ACM 24, 18-23, 772 (1981; Zbl 0454.68084)].   In the `Exclusive Read, Exclusive Write' algebraic parallel random access model of computation, the first algorithm uses \\(O(\\log n)\\) time and \\(O(n/(\\log n\\log\\log n))\\) processors. It is based on a sequential algorithm of \\textit{P. Pritchard} [Sci. Comput. Program. 9, 17-35 (1987; Zbl 0627.68033)].   The second algorithm uses \\(O (\\sqrt n)\\) time and \\(O (\\sqrt n)\\) processors, so it is theoretically less efficient. However, because of the absence of very fine-grained parallelism, it may be more efficient in practice. This observation is formalized by analyzing both algorithms in a model of parallel computation that allows for the communication latency inherent in a globally shared memory [\\textit{A. Aggarwal}, \\textit{A. K. Chandra}, \\textit{M. Snir}, Annual ACM Symposium on parallel algorithms and architectures, 1, 11-21 (1989)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336051$FA460628-6140-47C2-8C24-DE54FCE10E5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$8FE49915-FE59-40B6-AFA7-F84E858BAB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$ABED5DA9-5F8C-418E-9174-C3D5C6AC43C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecf21397fdcced4e2aeef35f7ab4217f79a7d6ec","datavalue":{"value":"11Y11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$CE7E6164-93FC-4C68-A30F-2FFEFD809E80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc134d939c061ac7baed403011e33cfb1701ba41","datavalue":{"value":"653290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$3D6E1455-E339-4A79-B3AC-6C6BC940B823","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a87b48f6cd462f82258677b911cbc3606161df9","datavalue":{"value":"globally shared memory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336051$B6174C7A-5F05-48B9-A190-47A81A1083B3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"da821cffe7e96269025b8e6783fb2f14735ef92b","datavalue":{"value":{"entity-type":"item","numeric-id":685523,"id":"Q685523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$B8311BAF-EA82-4993-AC60-EA4AB02C1661","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336051$A411088C-6298-407F-9D76-28499DE37CFE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bdf36b2e50f801114ed31c737fe1f6ebe3586e42","datavalue":{"value":"https://doi.org/10.1006/inco.1994.1082","type":"string"},"datatype":"url"},"type":"statement","id":"Q1336051$093B3051-8CBD-42C2-861E-5FBD23812A6A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"26cb102e8dd6df02e37d836e0d55326d3c6ba2fe","datavalue":{"value":"W1996893421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$BAC411FF-F1BA-4281-9239-CAA2F00FA6FC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa0c6a28f22df68ade91d9988e1b0f33f3bceb94","datavalue":{"value":"10.1006/INCO.1994.1082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336051$FF3A6F56-3C28-4A76-AB86-805576CE698C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fba835c511662c235a9ad8e18e4863251c8b728","datavalue":{"value":{"entity-type":"item","numeric-id":671385,"id":"Q671385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94eac1ca4c08acfdbc04ee426dfe7353e4c80aa3","datavalue":{"value":{"amount":"+0.8183935284614563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336051$AB0C1A8D-B716-4E6B-9807-61EE93450036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f12e184bd582b5171755c4c35f8976443661c778","datavalue":{"value":{"entity-type":"item","numeric-id":3337529,"id":"Q3337529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed07bfd76ecc16eebec50a8d8da66a5be5057861","datavalue":{"value":{"amount":"+0.8076208829879761","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336051$99D83001-84B6-4487-AEF0-0770EDA01E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19d0532082bb9ca1e0c8688f7bb6312ab97bfd1e","datavalue":{"value":{"entity-type":"item","numeric-id":1092658,"id":"Q1092658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dc378cd5e195f970859ccc282c8d05c45816cf9","datavalue":{"value":{"amount":"+0.8045188784599304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336051$D46A7064-8610-4AF2-8621-BD736808B6D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c623b62ead17031d30c42bbfa16f157b3ce5ce49","datavalue":{"value":{"entity-type":"item","numeric-id":3840160,"id":"Q3840160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b41a91551b3dec2967fca4a730080db476cbb92e","datavalue":{"value":{"amount":"+0.786755383014679","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336051$82B6DE32-99D7-4320-967E-3B1443E1F59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbc809f1a7b893e6c25e658e1c404b9899b412b3","datavalue":{"value":{"entity-type":"item","numeric-id":3105103,"id":"Q3105103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9766e975b23fabd7e15df487012812d5ea5c2daf","datavalue":{"value":{"amount":"+0.7865075469017029","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1336051$B311FF23-9537-4477-BEE5-B1A18DA6289A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two fast parallel prime number sieves","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_fast_parallel_prime_number_sieves"}}}}}