Added Segmented Sieve of Eratosthenes [C++] #486

manish1997 · 2017-10-03T08:26:03Z

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

Fixes #485

By submitting this pull request I confirm I've read and complied with the below declarations.

I have read the Contribution guidelines and I am confident that my PR reflects them.
I have followed the coding guidelines for this project.
My code follows the skeleton code structure.
This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
This pull request will be closed if I fail to update it even once in a continuous time span of 7 days.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

singhpratyush · 2017-10-03T08:26:04Z

Hi! Thanks for showing interest in contributing to this repository.

Please make sure that you have ticked the points mentioned in PR description correctly.

Thanks again!

manish1997 · 2017-10-03T08:40:29Z

@singhpratyush continuous-integration/travis-ci/pr is showing build failed because of some indentation problem.. How can one resolve this? Please check and tell where did it go wrong. :) I don't think this is a problem.

Monal5031 · 2017-10-03T08:49:23Z

@manish1997 I checked your travis log, it seems that you have used spaces for indentation but we use tabs for C and CPP, to pass the tests you need to indent your whole code with tabs.

manish1997 · 2017-10-03T10:46:12Z

@Monal5031 I edited the code to have only tabs. Still showing error.. Can you provide exact location to 2-3 points where this error is present? One example:
[56:01] ❌️ invalid indent style: space, expected: tab (EditorConfig indent_style https://github.com/editorconfig/editorconfig/wiki/EditorConfig-Properties#indent_style)
56| return 0;

I have used tab here. How to correct this.

manish1997 · 2017-10-03T11:31:24Z

@Monal5031 @singhpratyush Finally continuous-integration/travis-ci/pr passed. Review the PR and merge it. :)

aashutoshrathi · 2017-10-05T08:35:21Z

@manish1997 Add an entry in README.md

aashutoshrathi · 2017-10-05T08:36:01Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

@@ -0,0 +1,57 @@
+//Code Copyright: Manish Kumar, E&C, IIT Roorkee


We don't have copyright comments for this repo 😅

manish1997 · 2017-10-05T21:02:15Z

@aashutoshrathi how to add in readme. Instructions not given in contribution.md .
Also should I remove copyright comment?

Monal5031 · 2017-10-05T23:01:43Z

@manish1997 Yes please remove the copyrights, and you can use
[:white_check_mark:](folder_name/file_name)
as reference to add entry in README, add it in respecive algo row and lang column.

singhpratyush

Please take a look at the comments below. The points where I mentioned about spaces are not compulsory but would be good if you can make them as it would become consistent with other codes.

singhpratyush · 2017-10-06T08:04:32Z

README.md

@@ -46,6 +46,7 @@ Community (college) maintained list of Algorithms and Data Structures implementa
 | [Rod Cutting Problem](http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/) | [:white_check_mark:](rod_cutting_problem/rod_cutting.c) | | [:white_check_mark:](rod_cutting_problem/RodCutting.java) | [:white_check_mark:](rod_cutting_problem/rod_cutting.py) | [:white_check_mark:](rod_cutting_problem/rod_cutting.go) | [:white_check_mark:](rod_cutting_problem/rodCuttingProblem.js) | |
 | [Shell Sort](https://en.wikipedia.org/wiki/Shellsort) | | [:white_check_mark:](shell_sort/ShellSort.cpp) | [:white_check_mark:](shell_sort/ShellSort.java) | [:white_check_mark:](/shell_sort/shell_sort.py) | [:white_check_mark:](shell_sort/shell_sort.go) | [:white_check_mark:](shell_sort/shellSort.js) | [:white_check_mark:](shell_sort/ShellSort.cs) |
 | [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) | [:white_check_mark:](sieve_of_eratosthenes/sieveOfEratosthenes.c) | | [:white_check_mark:](sieve_of_eratosthenes/SieveOfEratosthenes.java) | [:white_check_mark:](sieve_of_eratosthenes/sieve_of_eratosthenes.py) | [:white_check_mark:](sieve_of_eratosthenes/sieve_of_eratosthenes.go) | [:white_check_mark:](sieve_of_eratosthenes/sieveOfEratosthenes.js) | |
+| [Segmented Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) | |[:white_check_mark:](segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp)| | | | | | |


The algorithms are supposed to be in ascending order, so this should go up.

Or maybe you can put it as Sieve of Eratosthenes (Segmented) so that these two appear together and one can compare them.

singhpratyush · 2017-10-06T08:04:49Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+#include <vector>
+using namespace std;
+
+vector<int> Prime; //contains prime numbers uptop segMax


Please do not use global variables.

This is so that one can directly use Prime vector to find get all prime numbers just after calling segmentedSieve()..

singhpratyush · 2017-10-06T08:05:50Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+
+vector<int> Prime; //contains prime numbers uptop segMax
+void segmentedSieve(){
+	#define segMax 1000000 //till point you want to find Primes. Preferebly pow(10,x)


Better take this as a parameter to the function, instead of hardcoding it.

sure will change it

singhpratyush · 2017-10-06T08:06:19Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+		high += rootSegMax;
+	}
+}
+int main(){


Please add line break between methods.

singhpratyush · 2017-10-06T08:06:38Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+		high += rootSegMax;
+	}
+}
+int main(){


int main(){ -> int main() {

Also make this change at other positions too, like with conditionals and loops. Have a space before {.

singhpratyush · 2017-10-06T08:06:57Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+	segmentedSieve(); //run it to find primes..
+	//Now Prime contains all the prime numbers upto segMax defined in function
+	for(int i = 0; i < Prime.size(); i++){
+		cout << Prime[i] <<" ";


Please add space around <<.

singhpratyush · 2017-10-06T08:09:20Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+	// ^^ higher end of current block we are finding primes for
+	int tempMax = Prime.size();
+	// ^^All non prime numbers will be multiples of these numbers only
+	while(low < segMax){


Keep a space between ( and reserved keywords that use them.
while( -> while (.

I don't think it should be necessary. :)

manish1997 · 2017-10-06T20:36:15Z

@singhpratyush i will do changes by sunday :)

Monal5031 · 2017-10-10T21:54:56Z

@manish1997 Please resolve conflicts and make the requested changes.

manish1997 · 2017-10-11T09:52:52Z

@Monal5031 there were no conflicts when I made this PR first. Someone tried merging it and conflicts came. Please look into that. Will make the changes by evening.

manish1997 · 2017-10-11T10:20:09Z

@Monal5031 @singhpratyush check this now.

Monal5031

Few changes, rest of the code looks good

Monal5031 · 2017-10-11T10:55:05Z

README.md

@@ -46,8 +46,8 @@ Community (college) maintained list of Algorithms and Data Structures implementa
 | [Rod Cutting Problem](http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/) | [:white_check_mark:](rod_cutting_problem/rod_cutting.c) | | [:white_check_mark:](rod_cutting_problem/RodCutting.java) | [:white_check_mark:](rod_cutting_problem/rod_cutting.py) | [:white_check_mark:](rod_cutting_problem/rod_cutting.go) | [:white_check_mark:](rod_cutting_problem/rodCuttingProblem.js) | |
 | [Shell Sort](https://en.wikipedia.org/wiki/Shellsort) | | [:white_check_mark:](shell_sort/ShellSort.cpp) | [:white_check_mark:](shell_sort/ShellSort.java) | [:white_check_mark:](/shell_sort/shell_sort.py) | [:white_check_mark:](shell_sort/shell_sort.go) | [:white_check_mark:](shell_sort/shellSort.js) | [:white_check_mark:](shell_sort/ShellSort.cs) |
 | [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) | [:white_check_mark:](sieve_of_eratosthenes/sieveOfEratosthenes.c) | | [:white_check_mark:](sieve_of_eratosthenes/SieveOfEratosthenes.java) | [:white_check_mark:](sieve_of_eratosthenes/sieve_of_eratosthenes.py) | [:white_check_mark:](sieve_of_eratosthenes/sieve_of_eratosthenes.go) | [:white_check_mark:](sieve_of_eratosthenes/sieveOfEratosthenes.js) | |
-| [Sleep Sort](http://www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/) | | [:white_check_mark:](sleep_sort/sleep_sort.cpp) | [:white_check_mark:](sleep_sort/SleepSort.java) | [:white_check_mark:](sleep_sort/sleep_sort.py) | [:white_check_mark:](sleep_sort/sleep_sort.go) | | | |
-
+| [Sieve of Eratosthenes (Segmented)](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) | |[:white_check_mark:](segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp)| | | | | | |


Shouldn't the file name also be segmented_sieve_of_eratosthenes?

@Monal5031 no. for c & c++ it should be like this.

Monal5031 · 2017-10-11T10:56:33Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+vector<int> segmentedSieve(int segMax) {
+	vector<int> Prime; //contains prime numbers uptop segMax
+	//segMax is point till you want to find Primes. ALWAYS pow(10,x)
+	int rootSegMax = sqrt(segMax); //root of segMax


Please follow standard C++ guidelines to name variables and functions throughout the code, use underscores to separate them rather than using camelCase

@Monal5031 is it really necessary? I don't think it will add any value.. if u think otherwise let me know

@manish1997 Sorry but we follow all the coding guidelines in this repository but we ignore many of them in ChefLib. This repo was made for learning purpose and well documented code is the best way to learn.

@Monal5031 okay, I understand. but I am habitual of this name convention and I don't think changing these will help me learn anything or it will help anyone else in learning it a better way. No offense :) Please close this PR & #494 :)

Monal5031 · 2017-10-11T10:58:38Z

segmented_sieve_of_eratosthenes/segmentedSieveOfEratosthenes.cpp

+#include <vector>
+using namespace std;
+
+vector<int> segmentedSieve(int segMax) {


Please document the function, see https://github.com/iiitv/algos/blob/master/binary_search/binary_search.c for reference.

singhpratyush · 2017-10-13T08:17:43Z

@manish1997: Please make the requested changes. Thanks.

Monal5031 · 2017-10-21T22:06:50Z

Closing this due to inactivity.

iiitv#485

25a4343

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

Monal5031 added Algorithm Hacktoberfest lang-cpp work in progress labels Oct 3, 2017

only tabs

ccc230f

Manish Kumar added 2 commits October 3, 2017 16:29

updated tabs

bb2fa5d

removed trailing spaces

a558c98

singhpratyush added the test/PASSING label Oct 3, 2017

singhpratyush requested review from Monal5031 and aashutoshrathi October 5, 2017 06:18

Merge branch 'master' into segmented_sieve

b56f7fa

singhpratyush removed the test/PASSING label Oct 5, 2017

aashutoshrathi changed the title ~~Added Algo/segmented_sieve_of_eratosthenes [C++]~~ Added Segmented Sieve of Eratosthenes [C++] Oct 5, 2017

aashutoshrathi reviewed Oct 5, 2017

View reviewed changes

Manish Kumar added 2 commits October 6, 2017 10:29

Update README.md

351325d

Update segmentedSieveOfEratosthenes.cpp

ef166cc

singhpratyush requested changes Oct 6, 2017

View reviewed changes

Update README.md

96682ae

Manish Kumar added 7 commits October 11, 2017 15:28

removed global variable

e6546e9

passed variable

43293d1

line break

27b9973

Update segmentedSieveOfEratosthenes.cpp

de44bb6

Update segmentedSieveOfEratosthenes.cpp

f4d5462

Update segmentedSieveOfEratosthenes.cpp

9107b3a

Merge branch 'master' into segmented_sieve

9cd6665

Monal5031 requested changes Oct 11, 2017

View reviewed changes

singhpratyush added the No activity label Oct 21, 2017

Monal5031 closed this Oct 21, 2017

singhpratyush removed the No activity label Oct 21, 2017

Monal5031 removed the Hacktoberfest label Oct 21, 2017

singhpratyush added the No activity label Dec 20, 2017

		@@ -0,0 +1,57 @@
		//Code Copyright: Manish Kumar, E&C, IIT Roorkee

Added Segmented Sieve of Eratosthenes [C++] #486

Added Segmented Sieve of Eratosthenes [C++] #486

Conversation

manish1997 commented Oct 3, 2017

By submitting this pull request I confirm I've read and complied with the below declarations.

singhpratyush commented Oct 3, 2017

manish1997 commented Oct 3, 2017

Monal5031 commented Oct 3, 2017

manish1997 commented Oct 3, 2017 • edited

manish1997 commented Oct 3, 2017

aashutoshrathi commented Oct 5, 2017

Choose a reason for hiding this comment

manish1997 commented Oct 5, 2017

Monal5031 commented Oct 5, 2017 • edited

singhpratyush left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

manish1997 commented Oct 6, 2017

Monal5031 commented Oct 10, 2017

manish1997 commented Oct 11, 2017

manish1997 commented Oct 11, 2017

Monal5031 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

singhpratyush commented Oct 13, 2017

Monal5031 commented Oct 21, 2017

manish1997 commented Oct 3, 2017 •

edited

Monal5031 commented Oct 5, 2017 •

edited